C++로 N까지의 교대 소수 출력하기

이 글에서는 C++를 사용해 N까지 존재하는 모든 교대 소수(alternate prime)를 출력하는 방법을 살펴봅니다. 교대 소수란 주어진 범위 안의 전체 소수 목록에서 한 개씩 건너뛰며 선택한 소수들을 의미합니다.

예를 들어 N = 15라고 가정해 보겠습니다. 15 이하의 소수는 {2, 3, 5, 7, 11, 13}이며, 이 중 교대 소수는 {2, 5, 11}입니다. 즉, 첫 번째 소수를 선택한 뒤 바로 다음 소수는 건너뛰고, 그다음 소수를 다시 선택하는 방식으로 진행됩니다.

알고리즘

printAlternatePrime(N)

Begin
    크기가 N + 1인 불리언 배열 prime을 선언하고 모든 요소를 1(true)로 초기화한다.
    p := 2부터 시작해 p² ≤ N인 동안 p를 1씩 증가시키며 반복:
        만약 prime[p]가 true라면,
            p의 모든 배수에 해당하는 위치를 prime 배열에서 0(false)으로 설정한다.
        조건문 끝
    반복문 끝
    플래그(flag)를 설정한다.
    p := 2부터 n까지 반복:
        만약 prime[p]가 true라면,
            플래그가 설정되어 있으면 p를 출력하고 플래그를 해제한다.
            그렇지 않으면 플래그를 다시 설정한다.
        조건문 끝
    반복문 끝
End

예제 코드

#include<iostream>
using namespace std;
void printAlternatePrime(int n) {
    bool prime[n + 1];
    for(int i = 0; i<=n; i++) {
        prime[i] = true;
    }
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * 2; i <= n; i += p) // 모든 배수를 false로 표시
                prime[i] = false;
        }
    }
    bool prime_flag = true;
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            if (prime_flag) {
                cout << p << " ";
                prime_flag = false;
            } else {
                prime_flag = true; // 다음 소수를 출력하기 위해 플래그 재설정
            }
        }
    }
}
main() {
    int n;
    cout << "상한값을 입력하세요: ";
    cin >> n;
    cout << "교대 소수: ";
    printAlternatePrime(n);
}

코드 설명

이 프로그램은 두 단계로 동작합니다. 첫 번째 단계에서는 에라토스테네스의 체(Sieve of Eratosthenes) 기법을 사용해 2부터 N까지의 모든 소수를 판별합니다. p²가 N 이하인 동안 각 소수 p의 배수들을 배열에서 모두 제거하면, 마지막에 true로 남은 숫자들이 곧 소수가 됩니다.

두 번째 단계에서는 불리언 변수 prime_flag를 활용해 교대 출력을 구현합니다. 소수를 만날 때마다 플래그 상태를 확인하여, 플래그가 설정되어 있으면 해당 소수를 출력한 뒤 플래그를 해제하고, 그렇지 않으면 플래그를 다시 설정합니다. 이 과정을 반복하면 소수를 하나 출력할 때마다 다음 소수는 자동으로 건너뛰게 됩니다.

이 알고리즘의 시간 복잡도는 O(N log log N), 공간 복잡도는 O(N)으로, 에라토스테네스의 체의 성능을 그대로 유지하면서 교대 출력 기능을 추가한 형태입니다.

실행 결과

상한값을 입력하세요: 20
교대 소수: 2 5 11 17