Python 判斷一個數是否為素數階乘素數

假設我們有一個數字 n，我們需要檢查 n 是否為素數階乘素數。如果一個數是 pN# + 1 或 pN# – 1 形式的素數，則稱其為素數階乘素數，其中 pN# 表示 pN 的素數階乘，即前 N 個素數的乘積。

因此，如果輸入是 29，則輸出為 True，因為當 N=3 時，29 是 pN - 1 形式的素數階乘素數，素數階乘為 2*3*5 = 30，而 30-1 = 29。

為了解決這個問題，我們將遵循以下步驟：

  • MAX := 100000
  • prime := 一個大小為 MAX 的列表，並用 True 填充
  • arr := 一個新的列表
  • 定義一個函式 SieveOfEratosthenes()。它將接收
  • for pri in range(2, int(MAX**0.5) + 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]:
      • 將 pri 新增到 arr 的末尾
  • 在主方法中，執行以下操作：
  • if prime[n] == 0:
    • return False
  • product := 1, i := 0
  • while product < n:
    • product := product * arr[i]
    • if product + 1 == n or product - 1 == n:
      • return True
    • i := i + 1
  • return 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

更新於：2020年8月27日

705 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告