에라토스테네스의 체

Sogang ACM-ICPC Wiki
이동: 둘러보기, 검색
에라토스테네스의 체

에라토스테네스의 체는 어떤 임의의 자연수까지의 모든 소수를 구하는 알고리즘이다. 시간 복잡도, 공간 복잡도이다.

알고리즘

  1. 2부터 소수를 구하고자 하는 구간까지의 모든 수를 나열한다.
  2. 2를 제외한 2의 배수를 전부 지운다.
  3. 3을 제외한 3의 배수를 전부 지운다.
  4. 4는 2의 배수로 이미 지워져 있으므로 다음 수인 5를 제외한 5의 배수를 전부 지운다.
  5. 위 과정을 반복한다.

구현

n까지의 소수 여부 배열만 필요할 경우 아래와 같이 구현하면 된다.

 1 #include <vector>
 2 
 3 using namespace std;
 4 ...
 5 vector<bool> sieve(n + 1);
 6 sieve[0] = true;
 7 sieve[1] = true;
 8 
 9 for (int i = 2; i * i <= n; i++) {
10     if (!sieve[i]) {
11          for (int j = i * 2; j <= n; j += i) {
12              sieve[j] = true;
13          }
14     }
15 }

이 과정을 거치면 sieve의 각 인덱스의 값을 반전하면 그 인덱스의 소수 여부가 저장되어 있다. 예를 들어 !sieve[3]true, !sieve[4]false 등이다.

n까지의 소수들의 배열이 필요할 경우 아래와 같이 구현하면 된다.

 1 #include <vector>
 2 
 3 using namespace std;
 4 ...
 5 vector<bool> sieve(n + 1);
 6 vector<int> primes;
 7 sieve[0] = true;
 8 sieve[1] = true;
 9 
10 for (int i = 2; i <= n; i++) {
11     if (!sieve[i]) {
12          primes.push_back(i);
13          for (int j = i * 2; j <= n; j += i) {
14              sieve[j] = true;
15          }
16     }
17 }