폐구간[1,n] 소수 구하기 (에라토스테네스의 체 - The Sieve of Eratosthenes)

< 소수 구하기 (에라토스테네스의 체) >

소수를 일반적인 방법으로 구한다면 아래와 같이 구할 수 있다.

어떤 값 N이 소수임을 판별하기 위해서는 2부터 N-1까지의 수로 나눠보면 된다.

이는 O(N)의 시간복잡도를 갖는다.

만약 1부터 N까지의 숫자가 소수임을 판별하기 위해서는

위와 같은 방법으로는 만큼의 시간이 걸린다.

이보다 빠른 방법은 없을까?

그 방법이 '에라토스테네스의 체'이다. (시간복잡도는 이다.)

1부터 10만까지의 숫자중에 소수인 숫자를 골라내려고 할 때,

에라토스테네스의 체를 이용하여 구하는 방법은 아래와 같다.

2부터 시작한다.

2는 소수인데, 2x (x>1)는 소수가 아니다.

그러므로 우리는 2를 약수로 갖는 모든 숫자를 체크할 수 있다.

이는 소수가 아닌 숫자를 체크하는 것인데,

간단하게 C++ 언어로 나타내면 다음과 같다.

#include <cstdio>
#include <cstring>
using namespace std;
bool isPrime[100001];
int main() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0]=isPrime[1]=false;
    for(int i=2; i<=100000; i+=2) {
        if(i==2) continue;
        isPrime[i] = false;
    }
    return 0;
}

이와 같은 방법으로 3에 대해서도 구해본다.

3은 소수이지만, 3x (x>1)는 소수가 아니다.

여기까지 코드로 나타내면 아래와 같다.

#include <cstdio>
#include <cstring>
using namespace std;
bool isPrime[100001];
int main() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0]=isPrime[1]=false;
    for(int i=2; i<=3; i++) {
        for(int j=i; j<=100000; j+=i) {
            if(j==2 || j==3) continue;
            isPrime[j] = false;
        }
    }
    return 0;
}

위와 같은 방법으로 4에 대해서도 구해보자.

하지만 조금만 생각해봐도 4에 대해서는 구할 필요가 없음을 알게된다.

왜냐하면 4x(x>1)는 2x(x>1)를 체크할 때 이미 체크가 되었기 때문에 isPrime[4x] = false;를 해줄 필요가 없다.

즉, 이미 isPrime[4]는 false가 되었기 때문에 isPrime[4x]에 대해서는 더이상 위의 알고리즘을 시행할 필요가 없다.

이를 1부터 10만까지의 숫자에 대해 모두 적용하면 아래와 같이 구현할 수 있다.

#include <cstdio>
#include <cstring>
using namespace std;
bool isPrime[100001];
int main() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0]=isPrime[1]=false;
    for(int i=2; i<=100000; i++) {
        if(!isPrime[i]) continue;
        for(int j=i*2; j<=100000; j+=i) {
            isPrime[j] = false;
        }
    }
    return 0;
}

하지만 이것만으로는 부족하다.

시간을 더 줄일 수 있다.

잘 생각해보면 for반복문에서 i값이 2부터 10만까지 돌 필요가 없다.

i값은 1부터 까지만 돌면 되는 것이다.

그 이유는 다음과 같다.

만약 이 소수라고 가정해보자.

그렇다면  (x>1)는 모두 소수가 아니다.

여기서 x가 1부터 까지는 이미 for반복문 에서 고려되었는데,

x가 이면 는 이므로 이는 N보다 큰 값이 된다.

따라서 for반복문의 i값은 1부터 까지만 돌면 되는 것이다.

그리고 for반복문의 j값도 i*2부터 시작할 필요가 없다.

i*i부터 시작하면 되는 것이다.

그 이유는 방금전에 언급한 이유와 같다.

j = i*x에서 x=1...i-1은 이전 반복문에서 모두 고려되었기 때문이다.

따라서 이를 올바르게 구현하면 아래와 같다.

(The Sieve of Eratosthenes: 폐구간 [1,n] 소수판별 - 시간복잡도: O(NlglgN))

#include <cstdio>
#include <cstring>
#include <cassert>
using namespace std;
typedef long long ll;
bool isPrime[100001];
int main() {
    ll n; scanf("%lld", &n);
    assert(1<=n && n<=100000);
 
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0]=isPrime[1]=false;
 
    for(ll i=2; i*i<=n; i++) {
        if(!isPrime[i]) continue;
        for(ll j=i*i; j<=n; j+=i) {
            isPrime[j]=false;
        }
    }
 
    int primeCnt=0;
    for(int i=1; i<=n; i++) {
        if(isPrime[i]) primeCnt++;
    }
    printf("prime count [1,%lld]: %d\n", n,primeCnt);
    return 0;
}

해당 방법은 아래의 위키피디아에 있는 그림을 참고하면 더 쉽게 이해할 수 있다.

https://ko.wikipedia.org/wiki/에라토스테네스의_체

그러면 1부터 N까지의 값이 아니라 어떤 특정값 x가 소수인지 빠르게 판별하는건 어떻게 할까?

이미 위에서 전부 설명이 되어있다.

('i값은 1부터 까지만 돌면 되는 것이다.' 부분 참고)

코드로 구현하면 다음과 같다.

#include <cstdio>
using namespace std;
typedef unsigned long long ull;
bool isPrime(ull n) {
    if(n<=1ULL) return false;
    else if(n==2ULL) return true;
    else if(n%2ULL == 0) return false;
    else {
        for(ull i=3ULL; i*i<=n; i+=2ULL) {
            if(n%i == 0ULL) return false;
        }
        return true;
    }
}
int main() {
    ull n; scanf("%llu", &n);
    if(isPrime(n)) printf("%llu is a prime\n",n);
    else printf("%llu isn't a prime\n", n);
    return 0;
}

한가지만 더해보면,

에라토스테네스의 체를 다음과 같이 비트마스크로 구현해서 메모리를 조금 줄일 수도 있다.

#include <stdio.h>
#include <cstring>
using namespace std;
#define TOTAL (1ULL<<23)
typedef unsigned long long ull;
typedef unsigned int uint;
char prime[(TOTAL+7U)>>3];
bool isPrime(unsigned int k) {
    return prime[k>>3] & (1U<<(k&7));
}
void setComposite(unsigned int k) {
    prime[k>>3] &= ~(1U<<(k&7));
}
int main() {
    ull n=TOTAL;
    memset(prime, 0xff, sizeof(prime));
    setComposite(0); setComposite(1);
    for(ull i=2ULL; i*i<=n; i++) {
        if(isPrime(i)) {
            for(ull j=i*i; j<=n; j+=i) {
                setComposite(j);
            }
        }
    }
    int d;
    while(true) {
        scanf("%d", &d);
        if(d<=0) return 0;
        if(isPrime(d)) printf("%d is a prime.\n",d);
        else printf("%d is not a prime.\n",d);
    }
    return 0;
}

위에서 pime[x]는 [8x, 8(x+1)) 구간이 소수인지 아닌지를 bit로 표시한 것이다.

만약 prime배열을 char type이 아닌 int type으로 한다면, 더 많은 공간을 절약할 수 있다.