C++로 소수를 찾는 가장 빠른 알고리즘 – 에라토스테네스의 체 완벽 정리

에라토스테네스의 체(Sieve of Eratosthenes)는 n이 약 1천만 이하일 때 n보다 작은 모든 소수를 찾는 가장 효율적인 방법 중 하나입니다. 이 알고리즘의 시간 복잡도는 O(n log log n)으로 매우 빠르며, 숫자 하나하나를 나누어 확인하는 단순 반복 방식보다 월등히 우수한 성능을 보여줍니다.

아래 프로그램은 에라토스테네스의 체를 구현한 예제입니다.

예제

#include <bits/stdc++.h>
using namespace std;

void SieveOfEratosthenes(int num) {
    bool pno[num + 1];
    memset(pno, true, sizeof(pno));
    for (int i = 2; i * i <= num; i++) {
        if (pno[i] == true) {
            for (int j = i * 2; j <= num; j += i)
                pno[j] = false;
        }
    }
    for (int i = 2; i <= num; i++)
        if (pno[i])
            cout << i << " ";
}

int main() {
    int num = 15;
    cout << "15 이하의 소수는 다음과 같습니다: ";
    SieveOfEratosthenes(num);
    return 0;
}

출력 결과

위 프로그램의 실행 결과는 다음과 같습니다.

15 이하의 소수는 다음과 같습니다: 2 3 5 7 11 13

이제 위 프로그램이 어떻게 동작하는지 자세히 살펴보겠습니다.

SieveOfEratosthenes() 함수의 동작 원리

SieveOfEratosthenes() 함수는 인자로 전달받은 num보다 작거나 같은 모든 소수를 찾습니다. 먼저 크기가 num+1인 불리언 배열 pno를 선언하고, memset() 함수를 사용해 모든 요소를 true로 초기화합니다. 초기값이 true라는 것은 "일단 모든 숫자를 소수 후보로 가정한다"는 의미입니다.

그다음 2부터 시작해 i의 제곱이 num 이하인 동안 반복합니다. 만약 pno[i]가 여전히 true라면 i는 소수이므로, i의 배수들은 모두 합성수임이 확실하기 때문에 해당 위치들의 값을 false로 바꿉니다. 외곽 반복문을 i*i까지만 돌리는 이유는, num 이하의 어떤 합성수도 반드시 √num 이하의 소수를 약수로 가지기 때문입니다. 이 최적화 덕분에 불필요한 연산을 크게 줄일 수 있습니다.

마지막으로 배열 전체를 순회하면서 값이 true로 남아 있는 인덱스, 즉 살아남은 소수들만 화면에 출력합니다.

void SieveOfEratosthenes(int num) {
    bool pno[num + 1];
    memset(pno, true, sizeof(pno));
    for (int i = 2; i * i <= num; i++) {
        if (pno[i] == true) {
            for (int j = i * 2; j <= num; j += i)
                pno[j] = false;
        }
    }
    for (int i = 2; i <= num; i++)
        if (pno[i])
            cout << i << " ";
}

main() 함수의 역할

main() 함수는 소수를 구할 범위를 나타내는 num 값을 설정한 뒤, SieveOfEratosthenes() 함수를 호출하여 num 이하의 모든 소수를 출력합니다. 위 예제에서는 num이 15이므로 2, 3, 5, 7, 11, 13이 차례대로 출력됩니다.

int main() {
    int num = 15;
    cout << "15 이하의 소수는 다음과 같습니다: ";
    SieveOfEratosthenes(num);
    return 0;
}

더 큰 범위를 다룰 때의 추가 최적화 팁

n이 수억 단위 이상으로 커지면 불리언 배열 하나만으로는 메모리 부담이 커질 수 있습니다. 이런 경우에는 비트셋(std::bitset 또는 bitarray)을 사용해 메모리 사용량을 8배까지 줄이거나, 범위를 나누어 처리하는 세그먼트 체(segmented sieve) 기법을 활용하는 것이 좋습니다. 또한 짝수를 아예 제외하고 홀수만 관리하는 방식(홀수 전용 체)을 적용하면 연산량과 메모리를 절반 수준으로 더 줄일 수 있습니다.

정리하자면, 대부분의 일반적인 상황에서 에라토스테네스의 체는 구현이 간단하면서도 매우 빠른 성능을 보장하기 때문에, C++에서 n 이하의 소수를 찾을 때 가장 먼저 고려할 최적의 선택이라 할 수 있습니다.