에라토스테네스의 체

소수를 가장 쉽게 판별하는 방법은 1부터 N까지 나눠보는 방법이다.

bool IsPrime(int N)
{
    if(N == 1)
        return false;

    for(int i = 2; i < N; i++)
        if(N % i == 0)
            return false;

    return true;
}

위의 방법은 $O(N)$의 시간복잡도를 보인다.
시간 제한이 조금만 타이트하더라도 사용하기엔 부담된다.

위의 방법을 조금 최적화할 수 있는 여지는 있다.
부등호를 활용하여 반복 범위를 줄이는 방법이다.

N의 약수를 a, b라고 한다면 다음과 같다.

$N = a \cdot b$

이때 a와 b가 N의 제곱근보다 크다고 가정해보자.

$a > \sqrt{N}, \quad b > \sqrt{N}$

그렇다면 N이 N보다 큰 경우이므로 이 경우는 모순이다.

$N = a \cdot b > \sqrt{N} \cdot \sqrt{N}$

즉, N의 약수는 $\sqrt{N}$보다 작다. 따라서 탐색 범위를 $\sqrt{N}$만큼으로 줄일 수 있다.

bool IsPrime(int N)
{
    if(N == 1)
        return false;

    for(int i = 2; i * i < N; i++)
        if(N % i == 0)
            return false;

    return true;
}

하지만 이 방법도 결국 $O(N)$의 시간 복잡도를 보인다.
에라토스테네스의 체를 이용하면 $O(N)$보다 빠르게 소수를 판별할 수 있다.

에라토스테네스의 체의 설명

에라토스테네스의 체는 닫힌 구간에서의 소수 판별을 구하는 데 효과적이다.
정리하기 위해 공부해본 결과 제일 오래된 소수를 구하는 방법이지만 제일 효율적이라고 한다.

기본적으로 이중 반복문을 사용하기 때문에 $O(N^2)$의 시간 복잡도를 가진다.
하지만 배수 제거로 인한 반복문의 생략문이 잦다.
실제로 에라토스테네스의 체의 시간 복잡도는 $O(N\cdot log(log N))$의 성능을 보인다.

에라토스테네스의 체의 원리

먼저 구하고자 하는 N의 크기만큼 1차원 배열을 생성한다.

vector<int> V(N + 1, INT_MAX);

2부터 시작해서 현재 선택한 숫자가 지워지지 않았다면 해당 숫자에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다.
이때 처음 선택한 숫자는 지우지 않는다.

vector<int> PrimeNumbers;

for(int i = 2; i <= N; i++)
{
    if(V[i] == 0)
    {
        PrimeNumbers.push_back(i);
        for(int j = i * 2; j <= N; j += i)
            V[j] = 1;
    }
}

에라토스테네스의 체의 최적화

앞선 소수를 선택하면서 꽤나 많은 배수들이 지워지기 때문에 반복문의 범위를 최적화할 수 있다.
현재는 i * 2부터 시작하지만 이를 i * i로 변경해도 무방하다.

vector<int> PrimeNumbers;

for(int i = 2; i <= N; i++)
{
    if(V[i] == 0)
    {
        PrimeNumbers.push_back(i);
        for(int j = i * i; j <= N; j += i)
            V[j] = 1;
    }
}

그리고 2의 배수를 제거하면서 홀수만 남기 때문에 바깥 반복문의 증가치를 최적화할 수도 있다.
현재는 i++지만 이를 i += 2로 변경해도 무방하다.

vector<int> PrimeNumbers;

PrimeNumbers.push_back(2);
for(int i = 3; i <= N; i += 2)
{
    if(V[i] == 0)
    {
        PrimeNumbers.push_back(i);
        for(int j = i * i; j <= N; j += i)
            V[j] = 1;
    }
}