에라토스테네스의 체

에라토스테네스의 체를 이용해 소수 판별하기 (C++)

주어진 범위 내에서 소수출력을 최대한 빠르게 할 수 있는 '에라토스테네스의 체' 알고리즘을 알아보겠습니다.

문제 : BOJ_1124번 언더프라임

백준 문제 1124번 언더프라임 문제인데요. 쉽게 말해서 언더프라임은 어떤 수를 소인수 분해 했을 때 나오는 소수의 개수가 소수인 수를 말합니다.
정해진 범위안에서 언더프라임을 구하기위해 많은 시도를 해볼 수 있겠지만, 결국 에라토스테네스의 체를 이용하지 않는다면 모두 시간초과에 걸린다는 것을 알게 됩니다.

그렇다면, 에라토스테네스의 체는 어떤 알고리즘일까요?

우선 120까지의 범위에서 에라토스테네스의 체를 사용하는 방법을 위키백과에서 발췌해 보겠습니다

에라토스테네스의 체 알고리즘

2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2는 소수이므로 2를 소수로 체크한다.
자기 자신을 제외한 2의 배수를 모두 지운다.
남아있는 수 가운데 3은 소수이므로 2을 소수로 체크한다.
자기 자신을 제외한 3의 배수를 모두 지운다.
남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 소수로 체크한다.
자기 자신을 제외한 5의 배수를 모두 지운다.
남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 소수로 체크한다.
자기 자신을 제외한 7의 배수를 모두 지운다.
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
그림의 경우, 이므로 11보다 작은 수의 배수들만 지워도 충분하다.
즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

(출처 : 위키백과)


에라토스테네스의 체는 말 그대로 소수를 제외한 수를 걸러내는 체이며, 문제에서 주어진 범위내에 소수들만 바로 걸러준다면 시간복잡도가 굉장히 줄어든다는 것을 알 수 있습니다.
간단하게 위의 120까지 소수출력 알고리즘을 c++로 만들어본다면,

알고리즘 구현

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int era[121];
int main(void) {
    era[0] = 1;
    era[1] = 1;
    for (int i = 2; i < sqrt(120); i++) {
        if (era[i] == 1) continue;
        int cnt = 2;
        while (cnt*i <= 120) {
            era[i*cnt] = 1;
            cnt++;
        }
    }
    for (int i = 1; i <= 120; i++) {
        if (era[i] == 0) cout << i << ' ';
    }
    return 0;
}

이렇게 배열에서 소수의 배수가 되는 수들은 모두 1로 바꿔주고 배열의 수가 0인 수들을 출력하면 소수가 출력됨을 알 수 있습니다. 여기서 더 시간복잡도를 줄이기위해 120이라면 11^2=121이기 떄문에, 반복문을 11까지만 돌렸음을 확인할 수 있고, 이는 주어진 범위에 따라 math.h의 sqrt()함수를 통해 구현할 수 있습니다.
그러면 다시 언더프라임 문제로 들어가서, sqrt()와 에라토스테네스의 체를 이용해 문제를 풀어본다면,

Solution code

#include <iostream>
#include <cmath>
using namespace std;
int era[100001], check[100001], nm1, nm2, cnt1, cnt2, res;;
int main(void) {
    cin >> nm1 >> nm2;
    for (int j = 2; j <= sqrt(nm2); j++) {
        if (check[j] == 0) {
            era[cnt1] = j;
            cnt1++;
            int mul = 2;
            int nm3 = mul * j;
            while (nm3 <= nm2) {
                check[nm3] = 1;
                mul++;
                nm3 = mul * j;
            }
        }
    }
    check[0] = 1;
    check[1] = 1;
    for (int i = nm1; i <= nm2; i++) {
        int nm4 = i;
        int st = 2;
        cnt2 = 0;
        while (nm4 != 1) {
            if (check[st] == 0) {
                if (nm4%st == 0) {
                    nm4 = nm4 / st;
                    cnt2++;
                }
                else st++;
            }
            else st++;
        }
        if (check[cnt2] == 0) res++;
    }
    printf("%d", res);
}

위와 같이 풀이하면, 1360ms로 시간복잡도에 위배되지않고 정답처리 됨을 알 수 있습니다.