C++ STL을 활용해 주어진 범위의 소수 출력하기

이 글에서는 C++ STL(표준 템플릿 라이브러리)을 활용하여 사용자가 지정한 범위 안에 있는 모든 소수(prime number)를 찾아 출력하는 프로그램을 다룹니다.
핵심 아이디어는 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘으로 0부터 각 경계값까지의 소수 목록을 두 개 만든 뒤, STL의 set_difference 함수로 두 목록의 차집합을 구하는 것입니다. 그러면 시작 값보다 크면서 끝 값 이하인 소수만 깔끔하게 남게 됩니다.

알고리즘

프로그램의 전체 흐름은 다음 세 단계로 구성됩니다.

1단계 — 0부터 n까지의 소수 구하기 (number 함수)

unsigned long long int를 stl이라는 이름으로 재정의(typedef)하고, stl 타입의 벡터 number를 준비합니다.
bool 타입 벡터 Prime_Number를 선언해 인덱스 0부터 a까지 모두 true로 초기화합니다.
Prime_Number[0]과 Prime_Number[1]은 false로 설정합니다. (0과 1은 소수가 아닙니다.)
정수형 변수 b에 √a 값을 저장한 뒤, pr을 2부터 b까지 증가시키며 Prime_Number[pr]이 true인 경우 pr*2부터 a까지 pr씩 건너뛰며 해당 위치를 false로 표시합니다.
탐색이 끝나면 Prime_Number[i]가 true인 i만 result 벡터에 push_back 하여 반환합니다.

2단계 — 불필요한 0 제거 (remove_zero 함수)

차집합 연산 결과 벡터에는 값이 채워지지 않은 빈 슬롯이 0으로 남을 수 있습니다. remove_zero 함수는 매개변수로 받은 값이 0이면 true를 반환하도록 선언되어, 이후 remove_if와 함께 사용됩니다.

3단계 — 차집합으로 범위 내 소수 추출 (Number_Range 함수)

stl 타입의 First_Num(시작 값)과 Last_Num(끝 값)을 매개변수로 받습니다.
s1 = number(First_Num): 0부터 First_Num까지의 소수 목록을 구합니다.
s2 = number(Last_Num): 0부터 Last_Num까지의 소수 목록을 구합니다.
크기가 Last_Num − First_Num인 결과 벡터 result를 선언합니다.
set_difference를 호출해 두 벡터의 차집합을 구합니다. 즉, Last_Num 이하의 소수 중 First_Num 이하의 소수를 제외한 값들이 result에 저장됩니다.
remove_if로 남아 있는 0을 제거한 뒤, itr − result.begin()으로 result의 크기를 조정하고 반환합니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int stl;

// 0부터 a까지의 소수를 구하는 함수 (에라토스테네스의 체)
vector<stl> number(stl a) {
    vector<bool> Prime_Number(a + 1, true);
    Prime_Number[0] = false;
    Prime_Number[1] = false;
    int b = sqrt(a);
    for (stl pr = 2; pr <= b; pr++) {
        if (Prime_Number[pr]) {
            for (stl i = pr * 2; i <= a; i += pr)
                Prime_Number[i] = false;
        }
    }
    vector<stl> result;
    for (int i = 0; i < a; i++)
        if (Prime_Number[i])
            result.push_back(i);
    return result;
}

// 벡터에서 0을 제거하기 위한 조건자(predicate) 함수
bool remove_zero(stl i) {
    return i == 0;
}

// [First_Num, Last_Num] 범위의 소수를 구하는 함수
vector<stl> Number_Range(stl First_Num, stl Last_Num) {
    vector<stl> s1 = number(First_Num);   // 0부터 First_Num까지의 소수
    vector<stl> s2 = number(Last_Num);    // 0부터 Last_Num까지의 소수
    vector<stl> result(Last_Num - First_Num);
    // 두 벡터의 차집합 계산
    set_difference(s2.begin(), s2.end(), s1.begin(), s1.end(), result.begin());
    // 남아 있는 0 제거 후 크기 조정
    vector<stl>::iterator itr = remove_if(result.begin(), result.end(), remove_zero);
    result.resize(itr - result.begin());
    return result;
}

int main(void) {
    stl First_Num = 20, Last_Num = 50;
    vector<stl> result = Number_Range(First_Num, Last_Num);
    cout << "The Prime Numbers from " << First_Num << " to " << Last_Num << " are: ";
    for (auto i : result)
        cout << i << ' ';
    return 0;
}

실행 결과

The Prime Numbers from 20 to 50 are: 23 29 31 37 41 43 47

20부터 50 사이의 소수인 23, 29, 31, 37, 41, 43, 47이 올바르게 출력되는 것을 확인할 수 있습니다.

핵심 포인트 정리

효율성: 에라토스테네스의 체의 시간 복잡도는 O(n log log n)으로, 각 수마다 일일이 나눗셈을 검사하는 방식보다 훨씬 빠릅니다.
set_difference: 두 정렬된 시퀀스의 차집합을 구하는 STL 알고리즘입니다. 입력 범위는 반드시 오름차순으로 정렬되어 있어야 하는데, 에라토스테네스의 체가 이미 오름차순 소수 목록을 만들어 주므로 그대로 사용할 수 있습니다.
remove_if의 동작: 요소를 실제로 삭제하지 않고 조건을 만족하지 않는 요소들을 앞쪽으로 이동시킨 후, 새로운 논리적 끝을 가리키는 반복자를 반환합니다. 따라서 resize(itr - result.begin())처럼 크기를 직접 줄이는 과정이 필요합니다.
안전한 크기 확보: 결과 벡터를 미리 Last_Num − First_Num 크기로 선언하면, 범위 내 소수 개수는 항상 범위 길이보다 작거나 같으므로 차집합 결과를 안전하게 담을 수 있습니다.