在 Python 中检查一个数是否为素数

pythonserver side programmingprogramming更新于 2025/10/17 8:12:17

假设我们有一个数 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() 。这将需要
对于 pri 在 2 到 int((MAX) 的平方根) + 1 范围内，执行
- 如果 prime[pri] 与 True 相同，则
  - 对于 i 在 pri * 2 到 MAX 范围内，在每个步骤中按 pri 更新，执行
    - prime[i] := False
对于 pri 在 2 到 MAX 范围内，执行
- 如果 prime[pri] 非零，则
  - 在 arr 末尾插入 pri
从主方法中，执行以下操作 −
如果 prime[n] 为零，则
- 返回 False
product := 1, i := 0
while product < n, do
- 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))