[에라토스테네스의 체] 소수 구하기

소수는 1과 나 자신으로만 나누어지는 수이다.

 

소수를 판별하는 알고리즘 중에서 에라토스테네스의 체가 가장 빠르다. ( 시간 복잡도 O(Nlog(logN)) )

 

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.

1. 배열을 생성하여 초기화한다.
2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
3. 2부터 시작하여 남아있는 수를 모두 출력한다.

여기서 한단계 더 발전시켜서 i*i까지 체크해준다. 

// i*i 부터 시작하는 이유는? 그이전 값은 그이전 i값에서 다 소수인지 체크 했으므로
// 3*3 = 9 부터 +3 씩 체크해주면된다, 2의배수는 2에서 모두 체크했음 5는 5에서 체크할 예정

 

static boolean[] prime = new boolean[1000001];
static void findPrime(){
        // 100만 이하 소수 찾기 prime[i] == false 소수
        for (int i = 2; i * i <= 1000000; i++) {
         // i*i 부터 시작하는 이유는? 그이전 값은 그이전 i값에서 다 소수인지 체크 했으므로
 		// 3*3 = 9 부터 +3 씩 체크해주면된다, 2의배수는 2에서 모두 체크했음 5는 5에서 체크할 예정
            if (!prime[i]) {
                for (int j = i * i; j <= 1000000; j += i) {
                    prime[j] = true;
                }
            }
        } 
}