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 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告