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

소수의 판별

1. 에라토스테네스의 체(Sieve of Eratosthenes) 란?

에라토스테네스의 체(Sieve of Eratosthenes)는 N보다 작거나 같은 모든 소수(Prime)를 찾을때 사용 하는 알고리즘 입니다.

 

 

2. 알고리즘 순서

1. 2부터 N까지의 모든 수를 나열 합니다.

2. 나열되어 있는 수 중에서 제거 되지 않은 가장 작은 수 i를 선택 합니다.

3. i를 제외한 i의 배수를 모두 제거 합니다. 

4. 2 ~ 3 과정을 반복 합니다.

5. 제거 되지 않고, 남아 있는 수가 소수 입니다.

 

 

3. 2부터 17까지의 자연수 중 소수를 모두 출력 하시오.

2부터 17까지의 모든 자연수를 나열 합니다.

 

 

첫번째 수인 2를 제외한 2의 배수를 모두 제거 합니다.

 

 

남아 있는 수 중에서, 다음 수인 3을 제외한 3의 배수를 모두 제거 합니다.

 

 

위와 같은 과정을 모두 끝까지 진행 하면, 위와 같은 수가 남습니다. 2, 3, 5, 7, 11, 13, 17이 모두 소수(Prime) 입니다. 

 

 

4. 에라토스테네스의 체(Sieve of Eratosthenes) java 소스 코드

import java.util.Arrays;

public class Eratosthenes {
    // 에라토네스의 체 (주어진 범위 내에서 소수 판별)
    public static void main(String[] args) {
        int n = 17;
        boolean[] array = new boolean[n + 1];
        Arrays.fill(array, true);

        Eratosthenes eratos = new Eratosthenes();
        boolean[] answers = eratos.isPrimeNumber(array);

        for (int i = 2; i < answers.length; i++) {
            if (answers[i]) {
                System.out.print(i);
                System.out.println();
            }
        }
    }

    public boolean[] isPrimeNumber(boolean[] array) {
        int n = array.length;
        int sqrtNum = (int) Math.sqrt(n);
        array[0] = false;

        // 약수의 대칭 성질을 이용해서
        // 제곱근 까지만 탐색
        for (int i = 2; i <= sqrtNum; i++) {
            // 소수인 경우
            if (array[i]) {
                // i를 제외한 i의 모든 배수 제거
                for (int j = 2; i * j < n; j++) {
                    array[i * j] = false;
                }
            }
        }
        return array;
    }
}

 

출력 결과

에라토스테네스의 체 역시도 약수(Divisor)의 대칭 성질을 이용해서, 제곱근 까지만 탐색 해도 해당 범위까지 소수(Prime)들을 찾아 낼수 있습니다. 에라토스테네스의 체의 시간 복잡도는 O(NloglogN)으로, 거의 선형 시간 이므로, 매우 빠르게 동작 합니다. 하지만, 해당 범위가 클 경우, 소수를 찾기 위한 해당 범위의 수들을 모두 메모리의 가지고 있어야 하므로, 메모리가 많이 필요하다는 단점이 있습니다.