에라토스테네스의 체(Sieve of Eratosthenes)는 구간 내의 소수를 빠르게 찾아야 할 때 사용되는 방법이다. 이것을 이용하면 여러 개의 수를 동시에 소인수분해하는 것도 가능하고, 더 응용하면 약수의 개수나 약수의 합 등을 빠르게 구하는 것도 가능하다.
에라토스테네스의 체를 이용하여 소수를 찾는 과정은 다음과 같다. 일단 소수를 구하려는 범위 내의 수를 차례로 나열한다. 여기서는 $n=120$이다.
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 37 38 39 40 41 42 43 44
45 46 47 48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63 64 65 66
67 68 69 70 71 72 73 74 75 76 77
78 79 80 81 82 83 84 85 86 87 88
89 90 91 92 93 94 95 96 97 98 99
100 101 102 103 104 105 106 107 108 109 110
111 112 113 114 115 116 117 118 119 120가장 먼저 $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 37 38 39 40 41 42 43 44
45 46 47 48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63 64 65 66
67 68 69 70 71 72 73 74 75 76 77
78 79 80 81 82 83 84 85 86 87 88
89 90 91 92 93 94 95 96 97 98 99
100 101 102 103 104 105 106 107 108 109 110
111 112 113 114 115 116 117 118 119 120다음으로 남아 있는 가장 작은 수는 $2$이다. $2$를 제외한 $2$의 배수를 모두 지운다.
2 3 5 7 9 11
13 15 17 19 21
23 25 27 29 31 33
35 37 39 41 43
45 47 49 51 53 55
57 59 61 63 65
67 69 71 73 75 77
79 81 83 85 87
89 91 93 95 97 99
101 103 105 107 109
111 113 115 117 119다음으로 남아 있는 가장 작은 수는 $3$이다. $3$을 제외한 $3$의 배수를 모두 지운다.
2 3 5 7 11
13 17 19
23 25 29 31
35 37 41 43
47 49 53 55
59 61 65
67 71 73 77
79 83 85
89 91 95 97
101 103 107 109
113 115 119다음으로 남아 있는 가장 작은 수는 $5$이다. $5$를 제외한 $5$의 배수를 모두 지운다.
2 3 5 7 11
13 17 19
23 29 31
37 41 43
47 49 53
59 61
67 71 73 77
79 83
89 91 97
101 103 107 109
113 119다음으로 남아 있는 가장 작은 수는 $7$이다. $7$을 제외한 $7$의 배수를 모두 지운다.
2 3 5 7 11
13 17 19
23 29 31
37 41 43
47 53
59 61
67 71 73
79 83
89 97
101 103 107 109
113다음으로 남아 있는 가장 작은 수는 $11$인데, $11$을 제외한 $11$의 배수가 존재하지 않으므로 지워지는 수가 없다. 이렇게 수가 하나도 지워지지 않을 때 반복을 종료하면 남은 수는 전부 소수가 된다.
에라토스테네스의 체의 구현은 다음과 같다. 보통 전처리 과정에서 등장하므로 따로 함수로 분리하지 않고 main 함수 내에 코드를 집어넣기도 한다.
int a[1000005];
void f(int n)
{
a[0] = a[1] = 1;
for(int i = 2; i * i <= n; i++)
{
if(!a[i])
{
for(int j = i * i; j <= n; j += i)a[j] = 1;
}
}
}$n$이 $100$만일 때 안쪽 for문의 총 반복 횟수는 $200$만 번 정도 된다. 중간의 if문을 생략했을 경우 반복 횟수는 약 $600$만 번으로 증가하므로 if문을 넣는 것이 성능에 약간 영향을 준다고 할 수 있다.
위와 같이 소수 여부를 판별만 하면 될 경우 $a$ 배열을 bool 배열로 선언하면 메모리를 절약할 수 있다. 하지만 int 배열로 선언하면 더 다양한 응용이 가능하다.
다음 코드는 $a[i]$에 $i$의 최소 소인수를 저장한다.
int a[1000005];
void f(int n)
{
for(int i = 2; i * i <= n; i++)
{
if(!a[i])
{
for(int j = i * i; j <= n; j += i)
{
if(!a[j])a[j] = i;
}
}
}
for(int i = 2; i <= n; i++)
{
if(!a[i])a[i] = i;
}
}이렇게 전처리를 했을 경우, 범위 내의 모든 수를 빠르게 소인수분해 할 수 있다. 다음 코드는 $v$에 $n$의 소인수분해 결과를 저장한다.
vector<int>v;
void f(int n)
{
while(n)
{
v.push_back(a[n]);
n /= a[n];
}
}약수와 관련된 정보를 저장할 때는 응용 방법이 약간 달라진다. 다음 코드는 $a[i]$에 $i$의 약수의 개수를 저장한다.
int a[1000005];
void f(int n)
{
for(int i = 1; i <= n; i++)
{
for(int j = i; j <= n; j += i)a[j]++;
}
}$a[i]$에 $i$의 약수의 합을 저장하려면 코드를 약간만 변형하면 된다.
int a[1000005];
void f(int n)
{
for(int i = 1; i <= n; i++)
{
for(int j = i; j <= n; j += i)a[j] += i;
}
}위의 두 코드에서 안쪽 반복문의 반복 횟수는 $n$이 $100$만일 때 약 $1400$만 번이다. 만약 다음과 같이 약수의 개수나 합을 구한다면, 안쪽 반복문의 반복 횟수는 $6$억 $6000$만 번을 넘어가는데다 느린 $\%$ 연산의 횟수가 증가하여 심각한 성능 저하를 초래하게 된다.
int a[1000005];
void f(int n)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j * j <= i; j++)
{
if(i % j == 0)a[i] += 2;
}
if(i * i <= n)a[i * i]--;
}
}이렇게 차이가 큰 이유는 두 방법의 시간복잡도가 다르기 때문이다. 에라토스테네스의 체는 기본적으로 $\Theta(n \text{ lg } n)$의 시간복잡도를 갖는 반면 나중 코드의 시간복잡도는 $\Theta(n\sqrt{n})$이다. 여기에 $n = 100$만을 대입할 경우 나오는 값은 $\Theta(n \text{ lg } n)$가 약 $2000$만, $\Theta(n\sqrt{n})$은 $10$억이고, 두 코드 모두 반복 횟수가 이것보다는 적지만 성능 차이를 보이는 것은 확실하다.
[연습문제]
에라토스테네스의 체로 $100$만 이하의 소수를 모두 구한 다음 입력된 구간 내의 소수를 차례로 출력한다.
$100$만 이하의 소수를 모두 구해 놓고, 각각의 수 $n$을 입력받으면서 $i$와 $(n - i)$가 모두 소수가 되는 가장 작은 $i$를 찾는다. 이건 그냥 하나씩 확인해도 된다.
BOJ 11439. 이항 계수 5 (Platinum IV)
$400$만 이하의 소수를 에라토스테네의 체로 모두 구한다. 그 다음으로 각각의 소수가 $_n\mathrm{C}_k$에 몇 번 곱해졌는지 계산한다.
CF 1528B. Kavi on Pairing Duty (1700)
입력 $n$에 대한 답이 $f(n)$일 때, $f(n) = f(1) + f(2) + ... + f(n - 2) + f(n - 1) + (n$의 약수의 개수$)$이다. $n$의 약수의 개수를 미리 구해 놓으면 문제를 풀 수 있다.
CF 1470B. Strange Definition (1900)
$ax^2 = by^2$일 때 $a$와 $b$는 adjecent하다. 따라서 $100$만 이하의 수에 대해 $a[i]$를 ($i$의 소인수의 각각의 지수에 $\text{%}2$ 연산을 취한 값)으로 정의하면 $a[i]$를 에라토스테네스의 체와 같은 방식으로 빠르게 구할 수 있다. $a[i]$가 같은 수는 서로 adjecent하다. 따라서 $n$개의 수를 $a[n]$이 같은 것끼리 묶으면, $1$초가 지나면 크기가 짝수인 묶음의 모든 원소는 곱해져서 $a[n]=1$인 묶음과 합쳐진다. 그 다음부터는 답에 영향이 없으므로 $w$가 $0$인 경우와 아닌 경우를 각각 처리하면 된다.
'Algorithm > D. Math & Number Theory' 카테고리의 다른 글
| 51. Extended Euclidean Algorithm (0) | 2021.06.03 |
|---|---|
| 50. Pigeonhole Principle (0) | 2021.06.02 |
| 48. Prime Factorization (0) | 2021.05.29 |
| 47. Probability (0) | 2021.05.16 |
| 46. Combinatorics (0) | 2021.05.15 |
