C++로 구현하는 숫자의 프리모리얼(Primorial) 계산 방법

이 문제에서는 하나의 숫자 n이 주어지며, 우리의 과제는 해당 숫자의 프리모리얼(Primorial) 값을 출력하는 것입니다.

프리모리얼 수(Pn#)란 처음 n개의 소수를 모두 곱한 값을 의미합니다.

프리모리얼은 일반적인 팩토리얼(factorial)과 매우 유사한 개념입니다. 차이점이 있다면, 팩토리얼은 1부터 n까지의 모든 자연수를 곱하는 반면, 프리모리얼은 오직 소수(prime number)만을 사용하여 곱셈을 수행한다는 점입니다.

구체적인 예시를 통해 문제를 이해해 보겠습니다.

입력: N = 4
출력: 210
설명: 프리모리얼 Pn# = 2 * 3 * 5 * 7 = 210

이 문제를 해결하기 위해서는 먼저 처음 n개의 소수를 찾아야 합니다. 그런 다음 n번째 소수까지의 모든 소수를 곱한 값, 즉 프리모리얼 값을 계산하여 출력하면 됩니다.

소수를 효율적으로 구하기 위해 위 코드에서는 에라토스테네스의 체(Sieve of Eratosthenes)를 최적화한 방식을 사용했습니다. 짝수인 2를 제외한 나머지 홀수들만 배열에 표시(marking)하여 메모리와 연산량을 줄일 수 있습니다.

예제 코드

다음은 위에서 설명한 풀이 방법을 C++로 구현한 프로그램입니다.

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000000;
vector <int> primeNumbers;
void findPrimes() {
    bool marked[MAX/2 + 1] = {0};
    for (int i = 1; i <= (sqrt(MAX)-1)/2 ; i++)
        for (int j = (i*(i+1))<<1 ; j <= MAX/2 ; j += 2*i +1)
            marked[j] = true;
    primeNumbers.push_back(2);
    for (int i=1; i<=MAX/2; i++)
        if (marked[i] == false)
            primeNumbers.push_back(2*i + 1);
}
int findPrimorial(int n) {
    findPrimes();
    int result = 1;
    for (int i=0; i<n; i++)
        result = result * primeNumbers[i];
    return result;
}
int main() {
    int N = 6;
    cout<<"Primorial(P#) of first "<<N<<" prime numbers is "<<findPrimorial(N)<<endl;
    return 0;
}

출력 결과

Primorial(P#) of first 6 prime numbers is 30030

코드 동작 원리 정리:

1. findPrimes() 함수가 에라토스테네스의 체를 활용하여 MAX 범위 내의 모든 소수를 미리 구해 벡터에 저장합니다.
2. findPrimorial(n) 함수는 저장된 소수 목록에서 처음 n개의 소수를 순서대로 곱하여 결과를 반환합니다.
3. N = 6인 경우, 2 × 3 × 5 × 7 × 11 × 13 = 30030이 출력됩니다.