49. Sieve of Eratosthenes

에라토스테네스의 체(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$억이고, 두 코드 모두 반복 횟수가 이것보다는 적지만 성능 차이를 보이는 것은 확실하다.

 

[연습문제]

 

BOJ 1929. 소수 구하기 (Silver II)

에라토스테네스의 체로 $100$만 이하의 소수를 모두 구한 다음 입력된 구간 내의 소수를 차례로 출력한다.

 

BOJ 6588. 골드바흐의 추측 (Silver I)

$100$만 이하의 소수를 모두 구해 놓고, 각각의 수 $n$을 입력받으면서 $i$와 $(n - i)$가 모두 소수가 되는 가장 작은 $i$를 찾는다. 이건 그냥 하나씩 확인해도 된다.

 

BOJ 17425. 약수의 합 (Gold V)

$100$만 이하의 각각의 수의 약수의 합을 위에서 설명한 방법대로 구하고, 누적합 형태로 변환한다. 이제 각각의 수를 입력받으면서 저장된 값을 출력한다.

 

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$인 경우와 아닌 경우를 각각 처리하면 된다.

 

→ solved.ac tag: sieve