[Algorithm] 에라토스테네스의 체 -JAVA

1. 에라토스테네스의 체

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법

이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 에라토스테네스의 체라고 부른다.

 

2. 방법

예시 1~144 범위에서 소수를 구하라

1. 소수도, 합성수도 아닌 자연수 1을 제거

 

2. 2를 제외한 2의 배수를 제거

 

3. 3을 제외한 3의 배수를 제거

 

4. 5를 제외한 5의 배수 제거 (4의 배수는 2의 배수에서 지워졌다.)

 

5. 7를 제외한 7의 배수 제거 (6의 배수는 2의 배수에서 지워졌다.)

 

6. 11를 제외한 11의 배수 제거 (8의 배수는 2의배수, 9의 배수는 3의 배수, 10은 2의배수에서 지워짐)

 

이런 방법으로 2배수, 3배수, ... n배수를 지우다보면 소수만 남게된다.

 

이런 방법으로 n이하의 소수를 모두 찾고 싶다면 1부터 n까지 쭉 나열한 다음에 제거한다.

 

특징

특정 범위 내의 소수를 판정하는 데에만 효율적이다.

 

구현

    private static void checkPrim(int M, int N){

        // 숫자를 채운다.
        for(int i=2; i<=N; i++){
            arr[i] = i;
        }

        // 자신을 제외한 배수 삭제
        for(int i=2; i <= N; i++){
            if(arr[i] == 0){
                continue;
            }

            for(int j=i+i; j<=N; j+=i){
                arr[j] = 0;
            }
        }
    }