Pythonで数値が階乗素数（Factorial Prime）かどうかを判定する方法

ある数値 n が与えられたとき、それが階乗素数（Factorial Prime）であるかどうかを判定する方法を解説します。

階乗素数とは？

階乗素数とは、「ある整数の階乗に対して 1 小さい数、または 1 大きい数」であり、かつ素数である数のことです。

例えば、入力が n = 719 の場合、出力は True になります。これは以下のように表せるためです。

719 = 720 − 1 = 6! − 1

判定アルゴリズムの手順

この問題は、次の手順で解くことができます。

• まず、num が素数であるかを確認します。素数でなければ False を返します。
• 変数を初期化します：factorial = 1、i = 1
• factorial <= num + 1 が成り立つ間、以下を繰り返します。
  • factorial = factorial * i として階乗を更新
  • num + 1 == factorial または num - 1 == factorial であれば True を返す
  • i = i + 1 としてカウンタを進める
• ループが終了しても該当しなければ False を返します。

Pythonでの実装例

理解を深めるために、実際の実装を見てみましょう。

from math import sqrt

def isPrime(num):
    if num <= 1:
        return False
    if num <= 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    for i in range(5, int(sqrt(num)) + 1, 6):
        if num % i == 0 or num % (i + 2) == 0:
            return False
    return True

def solve(num):
    if not isPrime(num):
        return False
    factorial = 1
    i = 1
    while factorial <= num + 1:
        factorial *= i
        if num + 1 == factorial or num - 1 == factorial:
            return True
        i += 1
    return False

num = 719
print(solve(num))

入力例

719

出力結果

True

処理のポイント

このコードでは、素数判定に「6k ± 1 最適化」を使用しています。2 と 3 の倍数を事前に除外した上で、√num までの範囲を 6 ずつ飛ばしながら確認することで、効率的に素数判定を行えます。その後、階乗を順次計算し、対象の数値が「階乗 ± 1」と一致するかを調べることで、階乗素数かどうかを正確に判定できます。