C++로 숫자가 프리모리얼 소수(Primorial Prime)인지 확인하는 방법

개념

주어진 양의 정수 n이 프리모리얼 소수(Primorial Prime)인지 판별하는 것이 과제입니다. n이 프리모리얼 소수라면 'YES'를 출력하고, 그렇지 않다면 'NO'를 출력해야 합니다.

프리모리얼 소수란? 수학에서 프리모리얼 소수는 pN# + 1 또는 pN# − 1 형태로 표현되는 소수를 의미합니다. 여기서 pN#은 '프리모리얼(primorial)'로, 처음 N개의 소수를 모두 곱한 값입니다.

예시 입력과 출력

입력: n = 7
출력: YES

7은 N=2일 때 pN + 1 형태의 프리모리얼 소수입니다. 프리모리얼 값은 2 × 3 = 6이며, 6 + 1 = 7이기 때문입니다.

입력: n = 29
출력: YES

29는 N=3일 때 pN − 1 형태의 프리모리얼 소수입니다. 프리모리얼 값은 2 × 3 × 5 = 30이며, 30 − 1 = 29이기 때문입니다.

참고로, 가장 작은 프리모리얼 소수들은 다음과 같습니다.

2, 3, 5, 7, 29, 31, 211, 2309, 2311, 30029

접근 방법

• 에라토스테네스의 체(Sieve of Eratosthenes)를 이용하여 탐색 범위 내의 모든 소수를 미리 구합니다.

• 먼저 n이 소수인지 확인합니다. n이 소수가 아니라면 즉시 'NO'를 출력합니다.

• n이 소수라면, 첫 번째 소수인 2부터 시작하여 다음 소수들을 차례대로 곱해 나가면서 매 단계마다 곱(product)에 대해 product + 1 = n 또는 product − 1 = n이 성립하는지 검사합니다.

• 두 조건 중 하나라도 만족하면 n은 프리모리얼 소수이고, 그렇지 않으면 프리모리얼 소수가 아닙니다.

C++ 구현 예제

// CPP program to check Primorial Prime
#include <bits/stdc++.h>
using namespace std;
#define MAX 10000
vector<int> arr1;
bool prime1[MAX];
void SieveOfEratosthenes1(){
    memset(prime1, true, sizeof(prime1));
    for (int p = 2; p * p < MAX; p++) {
        if (prime1[p] == true) {
            for (int i = p * 2; i < MAX; i += p)
                prime1[i] = false;
        }
    }
    for (int p = 2; p < MAX; p++)
        if (prime1[p])
            arr1.push_back(p);
}
bool isPrimorialPrime1(long n){
    // If n is not prime Number
    // return false
    if (!prime1[n])
        return false;
    long long product1 = 1;
    int i = 0;
    while (product1 < n) {
        product1 = product1 * arr1[i];
        if (product1 + 1 == n || product1 - 1 == n)
            return true;
        i++;
    }
    return false;
}
// Driver code
int main(){
    SieveOfEratosthenes1();
    long n = 29;
    // Check if n is Primorial Prime
    if (isPrimorialPrime1(n))
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}

실행 결과

YES

코드 설명

위 코드는 두 부분으로 구성됩니다. 첫째, SieveOfEratosthenes1() 함수는 에라토스테네스의 체를 사용해 MAX(10000)까지의 소수 여부를 배열에 저장하고, 소수만 별도의 벡터에 모읍니다. 둘째, isPrimorialPrime1() 함수는 입력값 n이 소수인지 먼저 검사한 뒤, 소수들을 순서대로 곱해가며 그 값이 n ± 1과 일치하는지 확인합니다. 시간 복잡도는 체 생성에 O(MAX log log MAX), 판별에는 소수 개수에 비례하는 선형 시간이 걸립니다.