에라토스테네스의 체는 소수(Prime Number) 를 찾는 방법이다. 대량의 소수들을 구해야할 때 아주 유용한 알고리즘으로 O(N^1/2)의 시간복잡도를 갖는다.
원리
소수란 약수가 오로지 1인 수이다. 즉, 1을 제외한 수의 배수가 되는 수는 소수가 아니다.
에라토스테네스의 체는 이러한 소수의 개념을 이용한 알고리즘이다.
임의의 수 n 까지의 소수를 구하고자 할 때 2부터 n의 제곱근까지 돌며 모든 배수들을 소수에서 제외시키는 방식이다.
알고리즘
우선 n까지의 소수를 구하고자 하면, n 크기의 배열을 만든다.
1
int primeNum[121]; // 120 까지의 소수를 구하고자 할 때
- 2는 소수이므로 그대로 두고 n까지 2의 배수들을 0으로 치환
ex) primeNum[4] = 0, primeNum[6] = 0 … - 3은 소수이므로 그대로 두고 n까지 3의 배수들 0으로 치환
- 4는 2번에서 0으로 치환 됐으므로 pass
- 위의 과정을 n의 제곱근에서 내림한 수까지 반복
ex) 11^2 > 120 이므로 11보다 작은 수의 배수들만 체크하면 된다 - 2 부터 n까지 0으로 치환되지 않은 수 출력
이제 소스 코드를 통해 직접 구현해보자.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cmath>
using namespace std;
int number = 120; // 구하고자 하는 소수의 범위
int primeNum[121];
void primeNumberSieve()
{
// primeNum 배열 초기화
for (int i = 2; i <= number; i++)
{
primeNum[i] = i;
}
for (int i = 2; i <= sqrt(number); i++)
{
// primeNum[i] 가 0이면 이미 소수가 아니므로 continue
if (primeNum[i] == 0)
continue;
// i*k (k<i) 까지의 수는 이미 검사했으므로 j는 i*i 부터 검사해준다.
for (int j = i * i; j <= number; j += i)
primeNum[j] = 0;
}
// 소수 출력
for (int i = 2; i <= number; i++)
{
if (primeNum[i] != 0)
printf("%d\n", primeNum[i]);
}
}
int main()
{
primeNumberSieve();
}
