Pythonで数値が素数階乗素であるかどうかを確認します

数nがあるとすると、nが素数階乗素であるかどうかを確認する必要があります。数がpN＃+ 1またはpN＃– 1の形式の素数である場合、その数は素数であると言われます。ここで、pN＃は、最初のN個の素数の積であるようなpNの素数を示します。

したがって、入力が29の場合、29はpN-1の形式の素数階乗素数であるため出力はTrueになります。N=3の場合、素数階乗は2 * 3 * 5 =30、30-1=29です。

これを解決するには、次の手順に従います-

• MAX：=100000
• prime：=サイズMAXのリストとTrueで埋める
• arr：=新しいリスト
• 関数SieveOfEratosthenes（）を定義します。これには時間がかかります
• 範囲2からint（（MAX）の平方根）+ 1のpriの場合、do
  • prime [pri]がTrueと同じ場合、
    • pri * 2からMAXの範囲のiの場合、各ステップでpriごとに更新します。
      • prime [i]：=False
• 2からMAXの範囲のpriについては、
  • prime [pri]がゼロ以外の場合、
    • arrの最後にpriを挿入
• メインの方法から、次の手順を実行します-
• prime [n]がゼロの場合、
  • Falseを返す
• product：=1、i：=0
• 製品
• product：=product * arr [i]
• product + 1がnと同じであるか、product-1がnと同じである場合、
  • Trueを返す
• i：=i + 1

例

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

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