C++로 N 이하의 모든 소수 사중주(Prime Quadruplet) 찾기

이 문제에서는 양의 정수 N이 주어지며, 우리는 N보다 작거나 같은 모든 소수 사중주(Prime Quadruplet)를 찾아 출력해야 합니다.

소수 사중주란?

소수 사중주는 {p, p⁺², p⁺⁶, p⁺⁸} 형태로 표현되는 네 개의 소수 집합을 의미합니다. 즉, 어떤 소수 p에 대해 p+2, p+6, p+8도 모두 소수일 때 이 네 수를 하나의 사중주라고 부릅니다.

예시: 5, 7, 11, 13은 소수 사중주입니다. (5+2=7, 5+6=11, 5+8=13이 모두 소수이기 때문입니다.)

문제 이해를 위한 예시

입력: N = 15
출력: 5 7 11 13

해결 접근 방법

방법 1: 단순 무차별 대입(Brute Force)

가장 간단한 방법은 가능한 모든 소수 p에 대해 p, p⁺², p⁺⁶, p⁺⁸이 모두 소수인지 일일이 검사하는 것입니다. 구현이 쉽다는 장점이 있지만, 매번 소수 여부를 반복해서 확인해야 하므로 컴파일러와 실행 시간 측면에서 비효율적입니다.

방법 2: 에라토스테네스의 체(Sieve of Eratosthenes) 활용

더 효율적인 방법은 에라토스테네스의 체를 사용하여 특정 범위까지의 모든 소수를 미리 구한 뒤 배열에 저장하는 것입니다. 그다음 배열을 순회하면서 각 위치 i에 대해 i, i+2, i+6, i+8이 모두 소수인지 확인하고, 네 수가 모두 소수라면 해당 사중주를 출력합니다.

이 방식은 소수 판별을 한 번만 수행하므로 전체 시간 복잡도가 크게 개선됩니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
bool prime[MAX];
void primeNumberGenerator() {
    memset(prime, true, sizeof(prime));
    for (int p = 2; p * p < MAX; p++) {
        if (prime[p] == true) {
            for (int i = p * 2; i < MAX; i += p)
                prime[i] = false;
        }
    }
}
void printPrimeQuadruplet(int n) {
    for (int i = 0; i < n - 7; i++) {
        if (prime[i] && prime[i + 2] && prime[i + 6] && prime[i + 8]) {
            cout<<i<<" "<<i+2<<" "<<i+6<<" "<<i+8<<endl;
        }
    }
}
int main() {
    primeNumberGenerator();
    int n = 42;
    cout<<"모든 소수 사중주 :\n";
    printPrimeQuadruplet(20);
    return 0;
}

출력 결과

모든 소수 사중주 :
5 7 11 13
11 13 17 19

코드 설명

primeNumberGenerator() 함수는 에라토스테네스의 체 알고리즘을 구현한 것으로, 2부터 시작해 각 소수의 배수들을 제거하며 MAX 범위까지의 소수 여부를 bool 배열에 저장합니다.

printPrimeQuadruplet() 함수는 0부터 n-7까지 반복하면서 현재 인덱스 i와 i+2, i+6, i+8 위치의 값이 모두 소수인지 검사합니다. 조건을 만족하면 해당 네 개의 소수를 화면에 출력합니다. 반복 범위를 n-7로 제한하는 이유는 i+8이 n을 초과하지 않도록 하기 위함입니다.

N = 20인 경우, 조건을 만족하는 소수 사중주는 {5, 7, 11, 13}과 {11, 13, 17, 19} 두 개입니다.