C++で素数階乗（プリモリアル）を求めるプログラムの解説

素数階乗（プリモリアル）とは？

この問題では、数値 n が与えられ、その素数階乗（プリモリアル）を求めて出力することが課題となります。

素数階乗（Primorial、Pn#）とは、「最初の n 個の素数をすべて掛け合わせた数」のことです。

素数階乗は、通常の階乗（n!）とよく似た概念です。両者の違いは、階乗が任意の整数を順に掛けるのに対し、素数階乗では素数のみを掛け合わせる点にあります。

問題の例

具体例を見てみましょう。

入力：N = 4
出力：210
説明：素数階乗 Pn# = 2 × 3 × 5 × 7 = 210

解き方のアプローチ

この問題を解くには、以下の手順で進めます。

1. 最初の n 個の素数をすべて求める
2. それらの素数の積を計算する
3. その積が素数階乗の値となるので出力する

素数の列挙には、エラトステネスの篩（ふるい）を最適化した手法を用いることで、効率よく素数リストを作成できます。

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

コードのポイント

• findPrimes() 関数：奇数のみを扱うことでメモリ使用量を半分に抑えたエラトステネスの篩を実装しています。まず 2 を素数リストに追加し、その後マークされていない奇数を素数として登録していきます。
• findPrimorial() 関数：生成した素数リストの先頭から n 個の素数を取り出し、順番に掛け合わせることで素数階乗を計算します。

なお、素数階乗は非常に大きな値になりやすいため、n が大きくなると int 型ではオーバーフローする可能性があります。実用上は long long 型や多倍長整数の利用を検討するとよいでしょう。