에라토스테네스의 체 (Sieve of Eratosthenes)

많은수의 소수 판변을 할때 유용한 방법

 

1. 가장 작은 소수를 찾기
2. 해당 수의 배수를 모두 지우기

 

 

 

 

 

 

 

 

 

 

 

boolean[] isNotPrime = new boolean[N + 1];

        isNotPrime[0] = true;
        isNotPrime[1] = true;

        for(int i = 2; i * i <= N; i++){
            if(!isNotPrime[i]){
                for(int j = i * i; j <= N; j += i){ //앞쪽에서 제거했기때문에 i*i부터 시작
                    isNotPrime[j] = true;
                }
            }
        }