에라토스테네스의 체

에라토스테네스의 체는 소수를 구하는 대표적인 알고리즘이며, 자주 쓰지만 쓸 때마다 헷갈려서 정리했다.

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define N 3000
int prime[N + 1];
 
void che() {
  prime[0] = -1;
  prime[1] = -1;
  for (int i = 2; i <= N; i++) prime[i] = i;
  int sqrtN = int(sqrt(N));
  for (int i = 2; i <= sqrtN; i++) {
    if (prime[i] == i) {
      for (int j = i * i; j <= N; j += i) {
        if (prime[j] == j) prime[j] = i;
      }
    }
  }
}
 
int main() {
  che();
  for (int i = 0; i <= N; i++) if (prime[i] == i) cout << prime[i] << '\n';
  return 0;
}

 

N은 소수의 범위를 결정한다. 예를 들어, N이 3,000이라면 3,000 이하의 소수를 구한다.

prime[] 배열의 원소는 index와 동일하게 둔다(line 13). 단, 0과 1은 소수가 될 수 없으므로 -1로 둔다.

 

소수인지 아닌지 판단은 root N까지만 하면 된다.

=> $N=p×q$라고 하자. 이 때 p와 q는 다음과 같은 모양을 띈다.

1. p == root N && q == root N

2. p < root N && q > root N

 

즉, 둘 중 적어도 하나는 root N보다 작거나 같다. 이 root N보다 작은 수의 배수는 소수가 아니라는 것을 소스코드에서 확인할 수 있다(line 15-17). root N보다 큰 수는 걸러지므로 root N까지만 확인하면 된다.