C++で数値が素数階乗素数（プリモリアル素数）かどうかを判定する方法

概念

正の整数 n が与えられたとき、n が「素数階乗素数（プリモリアル素数）」であるかどうかを判定するのが本記事の目的です。n が素数階乗素数であれば「YES」を、そうでなければ「NO」を出力します。

素数階乗素数とは：数学において、素数階乗素数とは p_N# + 1 または p_N# − 1 の形で表される素数のことです。ここで p_N# は最初の N 個の素数の積（素数階乗、プリモリアル）を表します。

入力例と出力例

入力： n = 7
出力： YES
n = 7 の場合、N = 2 のときの素数階乗は 2 × 3 = 6 であり、6 + 1 = 7 となるため、7 は p_N + 1 の形の素数階乗素数です。

入力： n = 29
出力： YES
n = 29 の場合、N = 3 のときの素数階乗は 2 × 3 × 5 = 30 であり、30 − 1 = 29 となるため、29 は p_N − 1 の形の素数階乗素数です。

参考までに、小さい方から順に並べた素数階乗素数は次の通りです。
2, 3, 5, 7, 29, 31, 211, 2309, 2311, 30029 …

アルゴリズムのアプローチ

• ステップ1：エラトステネスの篩（ふるい）を使って、指定した範囲内のすべての素数を生成します。
• ステップ2：n 自身が素数であるかを確認します。n が素数でなければ「NO」として処理を終了します。
• ステップ3：n が素数である場合、最初の素数 2 から順に次々と素数を掛け合わせて積を求めながら、「積 + 1 = n」または「積 − 1 = n」が成り立つかどうかを毎回チェックします。
• ステップ4：いずれかの条件が満たされれば n は素数階乗素数です。それ以外の場合は素数階乗素数ではありません。

C++での実装例

// 素数階乗素数を判定するC++プログラム
#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);
}

// nが素数階乗素数かどうかを判定する関数
bool isPrimorialPrime1(long n) {
    // nが素数でない場合は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;
}

// ドライバーコード
int main() {
    SieveOfEratosthenes1();
    long n = 29;
    // nが素数階乗素数かどうかをチェック
    if (isPrimorialPrime1(n))
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}

出力結果

YES

このプログラムでは、まずエラトステネスの篩によって MAX 未満の素数をすべて事前に計算し、配列に格納しています。その後、判定対象の数 n が素数であることを確認した上で、素数を順番に掛けていくことで n ± 1 との一致を調べます。計算量は篩の構築に O(MAX log log MAX)、判定部分は O(log n) 程度に抑えられ、非常に効率的な実装となっています。