[알고리즘] 에라토스테네스의 체 알고리즘

에라토스테네스의 체 (시간 복잡도O(N log log N) )

 

고대의 그리스 수학자 에라토스테네스에 의하여 개발된 정해진 범위 안의 소수를 찾는 알고리즘

 

2부터 N까지의 수를 적고 다음을 반복한다.

 

2부터 시작해 1씩 증가하면서 시작 수가 지워지지 않았다면 시작한 수를 제외하고 그 수의 배수를 모두 지운다. (배수들은 소수가 아니므로 지움)

 

 

출처: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity ​

 

 

시작 수를 정할때는 sqrt(N)까지만 보면 됩니다. (N이 소수임을 판별할 때 sqrt(N)까지만 보는 이유와 같음)

 

( sqrt(N) 소수 판정 알고리즘: https://seokjin2.tistory.com/17) )

 

배수를 지울때 시작 수의 제곱인 i*i 시작합니다.

 

왜냐하면 (2*i), (3*i), .... (i-1)(i)는 각각 2의 배수, 3의 배수, (i-1)의 배수에서 이미 지워졌기 때문에 그다음인 i*i부터 시작하면 됩니다,

 

<C++ 소스코드>

#include <iostream>
using namespace std;
 
#define MAX 100
int isPrime[MAX + 1];
 
void SieveOfEratosthenes() {
   for (int i = 2; i <= MAX; i++) {
      isPrime[i] = true; // 처음에 모두 소수라고 가정
   }
   for (int i = 2; i * i <= MAX; i++) { //2 부터 sqrt(n) 까지
      if (!isPrime[i]) continue; //이미 지워진 수는 무시
      for (int j = i * i; j <= MAX; j += i) { // 자기자신을 제외한 배수를 모두
         isPrime[j] = false; // 지운다
      }
   }
}
int main(void) {
    SieveOfEratosthenes();
    for (int i = 1; i <= MAX; i++) {
        if (isPrime[i])cout << i << ", ";
    }
   return 0;
}