C++로 1부터 n 사이의 소수의 합 구하기 – 기본 풀이부터 에라토스테네스의 체까지

문제 개요

이 문제에서는 하나의 수 n이 주어지며, 우리의 목표는 C++를 이용해 1부터 n 사이에 있는 모든 소수의 합을 구하는 프로그램을 작성하는 것입니다.

소수(Prime Number)란 약수가 정확히 두 개뿐인 수, 즉 1과 자기 자신만을 약수로 가지는 수를 의미합니다. 예를 들어 2, 3, 5, 7, 11, 13 등이 대표적인 소수입니다.

문제 이해를 위한 예시

입력

n = 15

출력

41

설명

1부터 15 사이의 소수는 2, 3, 5, 7, 11, 13이며, 이들의 합은 2 + 3 + 5 + 7 + 11 + 13 = 41입니다.

방법 1: 반복문과 소수 판별 함수 사용

가장 직관적인 풀이 방법은 반복문을 돌며 각 숫자가 소수인지 하나씩 검사하고, 소수인 값들을 모두 더하는 것입니다.

특정 수 i가 소수인지 판별하려면 2부터 √i까지의 수로 i를 나누어 보면 됩니다. 이 범위 안에서 나누어 떨어지는 수가 하나라도 존재하면 i는 소수가 아니며, 끝까지 나누어 떨어지는 수가 없다면 i는 소수입니다. √i까지만 검사해도 충분한 이유는, i의 약수 중 √i보다 큰 값이 존재한다면 반드시 √i보다 작은 짝이 되는 약수도 함께 존재하기 때문입니다.

구현 예제

#include <iostream>
using namespace std;

// 소수 여부를 판별하는 함수
bool isPrime(int n){
    if(n < 2)
        return false;
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

// 1부터 n까지의 소수의 합을 계산하는 함수
int findPrimeSum(int n){
    int sumVal = 0;
    for(int i = 2; i <= n; i++){
        if(isPrime(i))
            sumVal += i;
    }
    return sumVal;
}

int main(){
    int n = 15;
    cout << "1부터 " << n << " 사이의 소수의 합은 " << findPrimeSum(n) << " 입니다";
    return 0;
}

실행 결과

1부터 15 사이의 소수의 합은 41 입니다

이 방법은 구현이 간단하다는 장점이 있지만, 각 수마다 소수 여부를 개별적으로 검사해야 하기 때문에 시간 복잡도가 O(n√n)으로 다소 느린 편입니다.

방법 2: 에라토스테네스의 체 활용

더 효율적인 접근 방식은 에라토스테네스의 체(Sieve of Eratosthenes)를 사용하는 것입니다. 이 알고리즘은 2부터 시작해 각 소수의 배수들을 차례로 걸러내는 방식으로, 한 번의 전처리만으로 1부터 n까지의 모든 소수를 빠르게 구할 수 있습니다. 시간 복잡도는 O(n log log n)으로, n이 커질수록 단순 반복문 방식보다 월등히 빠른 성능을 보여줍니다.

구현 예제

#include <iostream>
#include <vector>
using namespace std;

// 에라토스테네스의 체를 이용해 1부터 n까지의 소수의 합을 구하는 함수
int findPrimeSum(int n){
    // sieve[i]가 true이면 i는 합성수(소수가 아님)
    vector<bool> sieve(n + 1, false);

    for(int i = 2; i * i <= n; i++){
        if(!sieve[i]){
            // i가 소수라면 i의 제곱부터 i의 배수를 모두 제거
            for(int j = i * i; j <= n; j += i){
                sieve[j] = true;
            }
        }
    }

    int sumVal = 0;
    for(int i = 2; i <= n; i++){
        if(!sieve[i])
            sumVal += i;
    }
    return sumVal;
}

int main(){
    int n = 15;
    cout << "1부터 " << n << " 사이의 소수의 합은 " << findPrimeSum(n) << " 입니다";
    return 0;
}

실행 결과

1부터 15 사이의 소수의 합은 41 입니다

마무리

두 방법 모두 동일한 결과를 얻을 수 있지만, n의 크기가 커질수록 에라토스테네스의 체를 사용한 방법이 훨씬 효율적입니다. 입력 범위가 작다면 단순 반복문 방식으로도 충분하지만, 성능이 중요한 상황이라면 에라토스테네스의 체를 활용하는 것이 좋은 선택입니다.