[Algorithm] 에라토스테네스의 체(Sieve of Erathosthenes)

에라토스테네스의 체(Sieve of Erathosthenes)

개념

에라토스테네스(BC273 - BC192)

• 지구의 둘레를 처음으로 계산한 고대 그리스 수학자 에라토스테네스(BC273 ~ BC192, Eratosthenes)가 기원전 200년에 고안한 방법으로, 아래와 같은 방법을 이용하여 소수를 구한다.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20

• 1은 소수가 아니라고 했으므로 우선 지워버린다.
• 다음으로 맨 처음 나오는 수(= 2)는 무조건 소수이다. 
  • 왜냐하면 약수가 1과 자기 자신밖에 없기 때문이다.
  • 그리고 2의 배수는 소수가 아니므로 모두 지워버린다.
• 다음으로 지워지지 않은 수들 중에서 가장 작은 수(= 3)를 찾는다.
  
  • 이렇게 지워지지 않고 남은 수는 소수이다. 
  • 왜냐하면 1이 아니면서 3보다 작은 약수가 있었다면 이미 지워졌기 때문이다. 
  • 3은 남기고, 나머지 3의 배수는 3 × 3부터 모두 지워버린다.
  • 3의 배수 6(= 3 × 2)은 이미 2의 배수일 때 지워졌기 때문에 3 × 3부터 3의 배수를 제거하면 된다.
• 다음으로 4는 이미 제거되었기 때문에 통과된다.
  • 그리고 4의 배수는 2의 배수일 때 제거되었기 때문에 4의 배수를 제거하는 작업은 필요 없다.
• 다음으로 지워지지 않은 수들 중에서 가장 작은 수(=5)를 찾는다.
  • 조금 전과 같은 이유로 5도 소수이다.
  • 그리고 5의 배수들을 5 × 5부터 모두 지워버린다.
    • 왜냐하면 10(= 5 × 2)은 2의 배수일 때 제거되었고, 15(= 5 × 3)는 3의 배수일 때 제거되었고, 20(= 5 × 4 = 10 × 2)은 2의 배수일 때 제거되었기 때문이다.
• 이 과정을 구하고자 하는 범위까지 반복한다면 지워지지 않고 남아있는 수들은 소수(Prime Number)이다.  

---

• 마치 채로 불순물을 걸러내는 것과 같다고 해서 '에라토스테네스의 체(Sieve of Eratosthenes)'라고 부른다.
• 지금은 컴퓨터를 이용해서 빠르게 소수를 구할 수 있지만, 숫자가 커진다면 소수를 구하는데 아주 오랜 시간이 걸린다.
• 지금까지 소수를 구하는 많은 방법이 나왔지만, 비교적 작은 소수(약 100만 이하)를 찾는 데는 에라토스테네스의 체보다 빠른 방법은 없다고 한다.

 

알고리즘

#include <iostream>
using namespace std;

int main() {
    int check[101] = { 0 };
    
    for (int i = 2; i <= 100; i++) {
        if (check[i] == 0) {
            cout << i << " ";
            for (int j = i * i; j <= 100; j += i) {
                check[j] = 1;
            }
        }
    }   
    return 0;
}

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

 

• check[i]에 0이 들어 있으면, 인덱스 i는 소수가 확정되었으므로 동그라미가 쳐진 것이고, check[i]의 값에 1이 들어 있으면 인덱스 i는 소수가 아니므로 제거되었음을 의미한다.
• 10번째 줄에서 j의 값이 i * 2가 아니라 i * i 부터 출발하는 이유?
  • 예) i = 3일 때, 3 * 2의 값은 i의 값이 2일 때 이미 2의 배수에서 제거되었기 때문에 i * i 부터 제거해 나가는 것이다.
• 이와 같은 방법으로 모든 소수가 구해질 때까지 처리하게 된다면, check 배열의 2번 인덱스의 값부터 100번 인덱스의 값까지 확인하였을 때 배열의 값이 0인 인덱스는 모두 소수가 된다.

 

예 : 2부터 50까지 범위 내에 존재하는 소수 구하기

단계 0	단계 1
2부터 50까지 범위 내에 존재하는 소수를 구해본다.	2를 제외한 2의 배수를 모두 제외한다.
단계 2	단계 3
3을 제외한 3의 배수를 모두 제외한다.	4의 배수는 앞서 1단계에서 모두 제외되었으므로, 5를 제외한 5의 배수를 모두 제외한다.
단계 4
앞선 단계들과 마찬가지로 아직 지워지지 않은 7의 배수, 11의 배수, ... 등을 지워나가면 최종적으로 소수들만 남게 된다.	따라서 2와 50사이에 존재하는 소수는 다음과 같다. [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

 

/* 2 이상 N 이하의 소수 구하기 */
int sieve[N];
sieve[0] = sieve[1] = 0;
for (int i = 2; i <= N; i++) {
    sieve[i] = i;
}

for (int i = 2; i <= N; i++) {
    if (sieve[i] == 0) {    // 이미 수가 지워진 경우 넘어간다.
        continue;
    }
    for (int j = i * i; j <= N; j += i) {    // 단계 1, 2, 3, ... 의 과정
        if (sieve[j] == 0) {    // 이미 수가 지워진 경우 넘어간다.
            continue;
        }
        else {
            sieve[j] = 0;    // 수를 지운다.
        }
    }
}

for (int i = 2; i <= N; i++) {
    if (sieve[i] != 0) {    // 배열의 요소값이 0이 아닌(지워지지 않은)
        cout << i << '\n'    // 인덱스를 출력한다.
    }
}

 

이미 구해진 소수를 이용하여 소수 구하기

• 어떤 수 n이 소수인지 판별하고자 할 때, 2부터 sqrt(n) 이하의 정수들로 n을 나누었을 때 나눌 수 있는 수가 없다면 n을 소수라고 판별할 수 있다.
  • 예) 100이 소수인지 판별하고자 할 때, 2부터 sqrt(100) 이하의 정수 2, 3, 4, 5, 6, 7, 8, 9, 10으로 나누어봐서 만약 100을 어떠한 수로도 나눌 수 없다면 100을 소수라고 판별할 수 있다.
• 여기에서 한 단계 더 생각해보면 4(= 2 × 2)로 나누어 떨어지는 수는 2로 나누어 떨어질 것이고, 6(= 2 × 3)으로 나누어 떨어지는 수는 2 또는 3으로 나누어 떨어질 것이며, 8(= 2 × 2 × 2)로 나누어 떨어지는 수는 2로 나누어 떨어질 것이고, 9(= 3 × 3)로 나누어 떨어지는 수는 3으로 나누어 떨어질 것이고, 10(= 2 × 5)으로 나누어 떨어지는 수는 2 또는 5로 나누어 떨어지게 되어 있다.
• 다시 말하면, 합성수(Composite Number)들은 소수들의 곱으로 이루어져 있으므로, 합성수를 제외한 소수들만으로 나누어서 나누어 떨어지지 않는다면 소수라고 할 수 있다는 것이다.
• 즉, 어떤 수 n이 소수인지 판별하고자 할 때, 2부터 sqrt(n) 이하의 소수들로 나누어 떨어지지 않는다면 n을 소수라고 판별할 수 있다.

 

알고리즘

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int cnt = 0, a[1000];
    int k, isPrime;
    
    for (int i = 2; i <= 1000; i++) {
        isPrime = 1;
        k = sqrt(i);
        for (int j = 1; j <= cnt && a[j] <= k && isPrime; j++) {
            if (i % a[j] == 0) {
                isPrime = 0;
            }
        }
        if (isPrime == 1) {
            a[++cnt] = i;    // 배열에 소수 채워 넣기
        }
    }
        
    for (int i = 1; i <= cnt; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

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 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997