C++로 구현하는 에라토스테네스의 체 – 주어진 범위에서 소수 생성하기

이 글에서는 C++로 에라토스테네스의 체(Sieve of Eratosthenes)를 구현하여 주어진 범위 안의 모든 소수를 생성하는 방법을 다룹니다.

에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 고안한 가장 고전적이면서도 효율적인 소수 판별 알고리즘입니다. 이 방법의 핵심 아이디어는 다음과 같습니다.

• 크기가 n인 정수 배열을 선언하고 모든 요소를 0으로 초기화합니다.
• 중첩 루프를 돌면서 각 수의 배수에 해당하는 인덱스(합성수)를 1로 표시합니다.
• 최종적으로 배열 값이 0으로 남아 있는 인덱스가 바로 소수입니다.

알고리즘

Begin
    Declare an array of size n and initialize it to zero
    Declare length, i, j
    Read length
    For i = 2 to n-1 do
        For j = i*i to n-1 step i do
            Arr[j-1] = 1
        Done
    Done
    For i = 1 to n do
        If(arr[i-1] == 0)
            Print i
    Done
End

알고리즘 동작 원리

바깥 루프는 2부터 시작하는 후보 수 i를 하나씩 늘려가며 검사하고, 안쪽 루프는 i의 제곱(i*i)부터 시작해 i씩 증가하며 i의 배수들을 모두 합성수로 표시합니다. i²부터 시작하는 이유는 i보다 작은 배수들은 이미 더 작은 소수의 배수로 처리되었기 때문입니다. 덕분에 불필요한 연산을 줄여 전체 시간 복잡도를 O(n log log n)까지 낮출 수 있습니다.

예제 코드

#include <iostream>
const int len = 30;
int main() {
    int arr[30] = {0};
    for (int i = 2; i < 30; i++) {
        for (int j = i * i; j < 30; j += i) {
            arr[j - 1] = 1;
        }
    }
    for (int i = 1; i < 30; i++) {
        if (arr[i - 1] == 0)
            std::cout << i << "\t";
    }
}

실행 결과

1  2  3  5  7  11  13  17  19  23  29

참고 사항

위 코드의 출력 결과에는 1이 포함되어 있습니다. 하지만 수학적으로 1은 소수가 아닙니다(소수는 1과 자기 자신 두 개의 양의 약수를 가진 2 이상의 자연수). 따라서 실제 프로젝트에서 사용할 때는 마지막 출력 루프를 i = 2부터 시작하도록 수정하는 것이 좋습니다.

또한 이 예제는 배열 크기를 상수(len = 30)로 고정했지만, 사용자로부터 범위를 입력받아 동적으로 처리하도록 확장할 수도 있습니다. 에라토스테네스의 체는 특정 범위 내의 모든 소수를 한 번에 구해야 할 때 가장 빠르고 널리 쓰이는 기법이므로, 코딩 테스트나 알고리즘 학습에 꼭 익혀두면 유용합니다.