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

ある数 n が与えられたとき、その n が「素数階乗素数（primorial prime）」であるかどうかを判定することを考えます。素数階乗素数とは、pN# + 1 または pN# − 1 の形で表される素数のことです。ここで pN# は pN の素数階乗（primorial）を表し、「最初の N 個の素数の積」として定義されます。

例えば、入力が 29 の場合、出力は True になります。N = 3 のとき素数階乗は 2 × 3 × 5 = 30 となり、30 − 1 = 29 であるため、29 は pN# − 1 の形の素数階乗素数に該当します。

なお、素数階乗素数の具体例としては、5（= 2×3−1）、7（= 2×3+1）、29、31、211 などが挙げられます。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• 上限値 MAX := 100000 とする
• prime := サイズ MAX のリストを作成し、すべて True で初期化する
• arr := 新しい空のリストを作成する
• 関数 SieveOfEratosthenes() を定義する。処理内容は次の通り：
  • pri を 2 から int(√MAX) + 1 まで繰り返す
    • prime[pri] が True の場合
      • i を pri × 2 から MAX まで pri 刻みで繰り返し、prime[i] を False に更新する
• pri を 2 から MAX まで繰り返し、prime[pri] が True であれば arr の末尾に pri を追加する

続いて、メインの判定処理では以下を行います。

• prime[n] が False（素数でない）の場合は False を返す
• product := 1、i := 0 と初期化する
• product < n の間、以下を繰り返す
  • product := product × arr[i]
  • product + 1 == n または product − 1 == n であれば True を返す
  • i := i + 1
• ループを抜けたら False を返す

実装例

以下の実装例を見て、理解を深めましょう。

from math import sqrt
MAX = 100000
prime = [True] * MAX
arr = []
def SieveOfEratosthenes() :
    for pri in range(2, int(sqrt(MAX)) + 1) :
        if prime[pri] == True :
            for i in range(pri * 2 , MAX, pri) :
                prime[i] = False
    for pri in range(2, MAX) :
        if prime[pri] :
            arr.append(pri)
def check_primorial_prime(n) :
    if not prime[n] :
        return False
    product, i = 1, 0
    while product < n :
        product *= arr[i]
        if product + 1 == n or product - 1 == n :
            return True
        i += 1
    return False
SieveOfEratosthenes()
n = 29
print(check_primorial_prime(n))

入力

29

出力

True