에라토스테네스의 체 ( 소수 [Prime Number] 판별 알고리즘 ) 예제

에라토스테네스의 체 알고리즘이란?

여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표 알고리즘이다. 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 알고리즘 순서는 다음과 같다.

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다 (i는 제거하지 않는다).
4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

예를 들어 N = 1000 일 때를 확인해보자.

 

[step1] 먼저 2부터 N(26)까지 모든 자연수를 나열한다. (1은 소수가 아니다)

[step2] 남은 수 중에서 아직 처리하지 않은 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거한다. 따러서 2를 제외한 2의 배수는 모두 제외한다.

[step3] 다음은 3을 제외한 3의 배수는 모두 제외한다.

[step4] 다음은 5를 제외한 5의 배수는 모두 제외한다.

[step5] 이어서 마찬가지로, 남은 수 중에서 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거하는 과정을 반복한다.

소수 판별 Java 소스 예제

아래 소스와 같이 i는 N의 제곱근(가운데 약수)까지만 증가시켜 확인하면 된다. 소수가 아닌경우 false값을 넣어준다.

에라토스테네스의 알고리즘은 메모리가 필요하다는 단점이 있어서 N이 커질수록 주의할 필요가 있다.

시간의 복잡도는 O(NloglogN)으로 사실상 선형 시간에 동작할 정도로 빠르다.

public class Solution {

    public static int n = 1000; // 2부터 1,000까지의 모든 수에 대하여 소수 판별
    public static boolean[] arr = new boolean[n + 1];

    public static void main(String[] args) {
        Arrays.fill(arr, true); // 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)
        // 에라토스테네스의 체 알고리즘 수행
        // 2부터 n의 제곱근까지의 모든 수를 확인하며
        for (int i = 2; i <= Math.sqrt(n); i++) {
            // i가 소수인 경우(남은 수인 경우)
            if (arr[i] == true) {
                // i를 제외한 i의 모든 배수를 지우기
                int j = 2;
                while (i * j <= n) {
                    arr[i * j] = false;
                    j += 1;
                }
            }
        }
        // 모든 소수 출력
        for (int i = 2; i <= n; i++) {
            if (arr[i]) System.out.print(i + " ");
        }
    }
}

References

「이것이 코딩테스트다」 - 한빛미디어 (나동빈 저)