JAVA n값 까지의 소수 갯수 구하기(에라토스테네스 체)

 

1. 2부터 시작
2. 2부터 시작했을 시 ch[2] == 0 이고 2는 소수이므로 answer++
3. answer를 더한 후 for문을 한번 더 돌리는데 도는 주기를 i를 더하여 i의 배수로 돌게 만들어준다
4. 이 배수들은 소수가 아니므로 값을 1로 바꾼다

 

int num = 20;

int answer = 0;

int[] ch = new int[num+1];

for (int i=2; i<=num; i++){

    if (ch[i] == 0){

        answer++;

        for (int j=i; j<=num; j=j+i){

            ch[j] = 1;

        }

    }

}