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

이 글에서는 C++ 표준 템플릿 라이브러리(STL)를 활용하여 주어진 범위 안의 모든 소수를 출력하는 프로그램을 살펴보겠습니다.

두 개의 수 a와 b가 주어졌을 때, 그 사이에 존재하는 모든 소수를 찾아 출력하는 것이 과제입니다. 이를 위해 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 서브루틴으로 실행하고, 구해진 소수들을 vector에 저장한 뒤 마지막에 한꺼번에 출력합니다.

접근 방식

핵심 아이디어는 다음과 같습니다.

시작값(start) 이하의 소수 전체 목록을 에라토스테네스의 체로 구합니다.
같은 방식으로 끝값(end) 이하의 소수 전체 목록을 구합니다.
STL의 set_difference 함수로 두 목록의 차집합을 계산하면, start보다 크고 end 이하인 소수만 남게 됩니다.
차집합 연산 과정에서 채워진 0(빈 자리)을 remove_if로 제거한 후 결과를 출력합니다.

예제 코드

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

// n 이하의 모든 소수를 구하는 에라토스테네스의 체
vector<unll> eratosthemes(unll n){
    vector<bool> prime_num(n+1,true);
    prime_num[0] = false;
    prime_num[1] = false;
    int m = sqrt(n);
    for (unll p=2; p<=m; p++){
        if (prime_num[p]){
            for (unll i=p*2; i<=n; i += p)
                prime_num[i] = false;
        }
    }
    vector<unll> elements;
    for (unll i=0; i<=n; i++)
        if (prime_num[i])
            elements.push_back(i);
    return elements;
}

// 0인 요소를 걸러내기 위한 조건자(predicate)
bool check_zero(unll i){
    return i == 0;
}

// [start, end] 범위에 속한 소수만 추출
vector<unll> sieve_range(unll start, unll end){
    vector<unll> s1 = eratosthemes(start);
    vector<unll> s2 = eratosthemes(end);
    vector<unll> elements(end-start);
    // 두 소수 목록의 차집합 계산
    set_difference(s2.begin(), s2.end(), s1.begin(),
    s1.end(), elements.begin());
    // 빈 자리로 남은 0 제거
    vector<unll>::iterator itr =
    remove_if(elements.begin(), elements.end(), check_zero);
    elements.resize(itr - elements.begin());
    return elements;
}

int main(void){
    unll start = 10;
    unll end = 90;
    vector<unll> elements = sieve_range(start, end);
    for (auto i : elements)
        cout<<i<<' ';
    return 0;
}

출력 결과

11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89

코드 설명

eratosthemes() 함수는 0부터 n까지의 수에 대해 소수 여부를 bool형 vector에 기록합니다. 2부터 √n까지의 수 p에 대해 p가 소수라면 p의 배수를 모두 소수가 아닌 것으로 표시하는 방식으로, 시간 복잡도는 O(n log log n)으로 매우 효율적입니다.

sieve_range() 함수는 start 이하의 소수 목록과 end 이하의 소수 목록을 각각 구한 뒤, 정렬된 두 집합에 set_difference를 적용해 차집합을 얻습니다. 그 결과 start보다 크고 end 이하인 소수만 남으며, remove_if와 resize로 빈 요소를 정리한 후 반환합니다.

예제에서는 10부터 90까지의 범위를 지정했으므로, 11부터 89 사이의 모든 소수가 공백으로 구분되어 출력됩니다.