소수 (2) - 에라토스테네스의 체 (Sieve of Eratosthenes)

1. 알고리즘 개요

 

[그림] 에라토스테네스의 체의 동작

 

에라토스테네스의 체는 정수 N까지의 모든 소수를 구하는 알고리즘이다. 일반적으로 소수 판별 알고리즘 중에서 가장 빠른 것으로 알려져있다. 알고리즘의 동작은 위 그림을 보면 쉽게 이해할 수 있다. 2부터 N-1까지 수의 배수들은 소수가 아닌 것으로 마크하고, 나머지 남은 수를 소수로 판별한다. 

 

---

Sieve of Eratosthenes

 

(1) 2 ~ N까지의 배열을 준비한다. 

 

(2) 정수 N을 입력받는다.

 

(3) 2 ~ N-1까지 수의 배수들의 인덱스를 1로 마크한다.

(속도향상 : 이미 인덱스가 1인 정수는 확인하지 않는다)

 

(3) 배열에서 인덱스가 0인 것을 소수로 판별한다. 

 

---

 

속도 향상을 위해 이미 인덱스가 1인 정수는 확인하지 않는다 (해당 수의 배수는 이미 그 수의 약수의 배수이다) 또한, 이전에 봤던 소수 알고리즘처럼 $X$까지의 소수를 알고싶을 때 2부터 $X-1$까지 전부 확인 할 필요 없이 $\sqrt{X}$ 까지만 확인하면 된다. 합성수 $X$가 $N \times M$으로 합성되고 이는 $M \times N$과 대칭관계를 이룬다 (자세한 예시는 여기 참고), 두 약수의 관계가 $N \geq M$이라고 할 때, 반드시 $N \geq \sqrt{X}$이고, $M \leq \sqrt{X}$이기 때문에 $\sqrt{X}$까지만 확인해봐도 그 전에 $M$이 약수로서 걸리게 되고, 때문에 소수 여부를 알 수 있게 된다.

 

2. 소스 코드

#include <cstdio>
#include <cmath>

int MAX = 10000;

int main() {
    int arr[MAX];
    for (int i = 0; i < MAX; i++) {
        arr[i] = 0;
    }

//  for (int i = 2; i < MAX; i++){           // slow
    for (int i = 2; i <= sqrt(MAX); i++) {   // fast

        if (arr[i] == 1) {
            continue;
        }

        for (int j = i * 2; j < MAX; j+=i) {
            arr[j] = 1;
        }
    }

    for(int i = 2 ; i < MAX ; i++){
        if(arr[i] == 0){
            printf("%d", i);

            if(i != MAX - 1){
                printf(" , ");
            }
        }
    }
    return 0;
}

 

gusdnd852/TIL

모든 소스코드는 Github에서 확인할 수 있습니다. 

3. Reference