C++에서 N 이하의 모든 소수 출력하는 방법 완벽 가이드

이 문제에서는 하나의 숫자 N이 주어지며, N보다 작거나 같은 모든 소수(prime number)를 찾아 출력해야 합니다.

문제 예시

입력: 10
출력: 2 3 5 7

소수란 무엇인가?

소수는 1과 자기 자신으로만 나누어 떨어지는 수를 의미합니다. 예를 들어 2와 3이 대표적인 소수입니다. 참고로 2는 유일한 짝수 소수라는 점도 기억해 두면 좋습니다.

접근 방법 1: 단순 반복 방식

가장 간단한 방법은 2부터 N까지 모든 숫자를 순회하면서 각 숫자를 2부터 차례대로 나누어 보는 것입니다. 만약 어떤 수로도 나누어 떨어지지 않는다면 그 수는 소수이므로 출력하면 됩니다. 이 과정을 N에 도달할 때까지 반복합니다.

하지만 이 방식은 모든 후보 숫자에 대해 불필요하게 많은 나눗셈을 수행하기 때문에 효율성이 떨어집니다.

접근 방법 2: √N까지만 검사하기 (효율적 방법)

훨씬 더 효과적인 방법은 소수 여부를 판별할 때 2부터 √N(제곱근)까지만 검사하는 것입니다. 어떤 합성수 n = a × b라고 할 때, a와 b 중 하나는 반드시 √n 이하이기 때문입니다. 따라서 √n까지 나누어 떨어지는 수가 없다면 n은 소수임을 확신할 수 있습니다.

추가 최적화로, 2와 3의 배수를 먼저 제거한 후 6k ± 1 형태의 숫자만 검사하면 연산 횟수를 크게 줄일 수 있습니다. 이는 5 이상의 모든 소수가 6의 배수에서 ±1 위치(즉, 5, 7, 11, 13, 17, 19...)에 존재하기 때문입니다.

C++ 구현 코드

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

bool isPrimeNumber(int n){
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    // 6k ± 1 형태의 숫자만 검사하여 효율성 향상
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}

void printPrime(int n){
    for (int i = 2; i <= n; i++) {
        if (isPrimeNumber(i))
            cout << i << " ";
    }
}

int main(){
    int n = 41;
    cout << "Prime numbers less than or equal to " << n << " are \n";
    printPrime(n);
}

실행 결과

41 이하의 소수는 다음과 같습니다:

2 3 5 7 11 13 17 19 23 29 31 37 41

시간 복잡도 분석

각 숫자의 소수 판별에 O(√n) 시간이 걸리므로, 2부터 N까지 전체를 검사하는 이 코드의 시간 복잡도는 O(N√N)입니다. 단순히 N까지 모두 나누어 보는 O(N²) 방식보다 상당히 개선된 성능을 보여줍니다.

만약 N이 매우 큰 경우(예: 10⁷ 이상)에는 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용하면 O(N log log N)의 시간 복잡도로 더욱 빠르게 모든 소수를 구할 수 있습니다.