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

에라토스테네스의 체는 특정 범위의 수들이 소수(Prime)인지 아닌지를 판별하는 알고리즘입니다. 

예를 들어 1부터 50까지 수 중에서 소수를 구하고자 한다면 다음과 같은 배열이 필요합니다.

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

먼저 가장 작은 소수인 2부터 시작합니다. 그리고 2의 배수에 해당하는 수들은 모두 소수가 아닙니다. 따라서 범위 안의 2의 배수들을 소수가 아니라고 체크해줍니다.(일반적으로 boolean타입이나 int형 변수를 만들어주어 체크) 아래에서 색이 칠해진 수는 소수가 아님을 나타냅니다.

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

다음은 3입니다. 3은 2의 배수가 아니므로 체크가 되어있지 않습니다. 따라서 3은 소수입니다. 아까 했던 방식처럼 범위 안의 3의 배수를 모두 소수가 아니라고 체크해줍니다.

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

다음은 4입니다. 4는 2의 배수를 체크할 때 체크된 숫자이므로 소수가 아닙니다. 따라서 그냥 넘어갑니다. 그러면 다음 수는 5입니다. 5는 체크된 숫자가 아니므로 소수입니다. 마찬가지로 5의 배수를 모두 체크 해줍니다.

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

다음 수인 6은 4와 마찬가지로 색이 칠해져 있습니다. 즉 6은 이미 어떤 소수의 배수였기 때문에 소수가 아니라는 것을 알 수 있습니다. 따라서 2부터 시작해서 구하고 싶은 최대값까지 차례대로 보며 남은 수 중 아직 지워지지 않은 가장 작은 값은 소수가 되며, 이 배수들을 지워나가면 우리는 범위 내의 모든 소수를 구할 수 있습니다.
위의 과정을 50까지 반복하면 배열은 아래와 같이 변하고, 이때 칠해지지 않은 수 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47이 1 ~ 50 범위에 속하는 소수가 됩니다.

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

이를 의사코드로 나타내면 다음과 같습니다.

Boolean Array isPrime[N]={true, …,true}
For(i=2;i<=N;i++)
{
   If(isPrime[i] is false) continue
   For(j=i+i;j<=N;j+=i)
   {
    	isPrime[j]=false
   }
} 	

위의 코드는 최적화가 가능합니다. 첫 번째 반복문의 범위를 1부터 N까지가 아닌 1부터 sqrt(N)까지라고 한다면 정확성은 유지하면서 속도가 좀 더 빨라집니다. 어째서 N이 아닌 sqrt(N)까지로 하는지 의문이 들 수 있으므로 추가 설명하겠습니다.
제곱인 숫자 A가 있다고 가정합시다. 어떤 수 A의 약수의 개수는 홀수 개 입니다 (만약 이 수가 어떤 수의 제곱이 아니라면 짝수 개가 되겠죠). 그리고 A의 전체 약수 집합이 {a1, a2, a3, a4, a5, a6, a7, a8}이었다고 한다면 이는 A = a1*a8 = a2*a7 = a3*a6 = a4*a5로 나타낸 수 있습니다.

즉, 어떤 수 N을 약수로 나눈 몫 또한 약수가 되게 되므로 해당 수가 어떤 수의 제곱이라면 왼쪽 그림과 같이 표현할 수 있고, 아니라면 오른쪽 그림과 같이 표현할 수 있습니다.

그러면 A의 약수를 구할 때 1부터 A까지가 아닌 1부터 sqrt(A)까지 구해야 된다는 것은 자명합니다. 따라서 N이 소수인지 아닌지 확인하기 위해 N 까지 확인하면 N의 약수들의 배수들이 소수인지 판별되었다는 것 또한 자명하기 때문에 이 알고리즘은 아래와 같이 최적화가 가능합니다.

Boolean Array isPrime[N]={true, …,true}
For(i=2;i<= sqrt(N);i++)
{
   If(isPrime[i] is false) continue
   For(j=i+i;j<=N;j+=i)
   {
    	isPrime[j]=false
   }
} 	
	

하지만 해당 범위 내에서 M번째 소수를 구하는 문제라면 위와 같이 최적화 해선 안됩니다. 위와 같이 최적화하고 범위 내의 소수를 구한다면 sqrt(N)까지 범위의 소수들만 구해지기 때문입니다. 따라서 해당 숫자가 소수인지 아닌지 판별할 경우에는 위와 같이 최적화하고 해당 소수를 출력하는 문제라면 최적화하지 않고 N까지 돌려야 합니다.

다음은 C++ 로 나타낸 코드입니다.

#include <iostream>
#include <cmath>
using namespace std;
#define MAX 1000000
bool isPrime[MAX+1];
int prime[MAX+1], cnt, num, testcase, T;

void sieve_Of_Eratosthenes(int N) {
    for (int i = 2; i <= N; i++) {
        isPrime[i] = 1;    // initialize isPrime[] array
    }
    int sqrtn=sqrt(N);
    for (int i = 2; i <= sqrtn; i++) {
        if (!isPrime[i]) continue;
        for (int j = i + i; j <= N; j += i) {
            isPrime[j] = 0;
        }
    }
}

int main() {
    sieve_Of_Eratosthenes(MAX);
    cin >> testcase;
    while (testcase != T) {
        T++;
        cin >> num;
        cout << "Case #" << T << endl;
        if (isPrime[num]) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

다음은 Java 로 나타낸 코드입니다.

import java.lang.Math;
import java.util.Scanner;;

public class Main {
    private final static int MAX = 1000000;
    static boolean isPrime[] = new boolean[MAX + 1];

    public static void main(String[] args) {
       
        Scanner scanner = new Scanner(System.in);
        for (int i = 2; i <= MAX; i++) {
            isPrime[i] = true;
        }

        int sqrtn = Math.sqrt(MAX);
        for (int i = 2; i <= sqrtn; i++) {
            if (!isPrime[i]) continue;
            for (int j = i + i; j <= MAX; j += i) {
                isPrime[j] = false;
            }
        }

        int testcase = scanner.nextInt();
        int T = 0, N = 0;
        while (testcase != T) {
            T++;
            N = scanner.nextInt();
            System.out.println("Case #" + T);
            if (isPrime[N]) {
                System.out.println("YES");
            }
            else {
                System.out.println("NO");
            }
        }
    }
}

다음 시간엔 이진 탐색에 대해 알아보겠습니다.