在Python中生成大素数

Question

我似乎无法使用此代码生成随机素数，请有人帮助我吗？

def RandomPrime():
  prime = False
  while prime == False:
    n = random.randint(10000, 100000)
    if n % 2 != 0:
      for x in range(3, int(n**0.5), 2):
        if n % x ==0:
          prime = False
        else:
          prime = True


  return n

Answer 1

想象一下，如果 range(3, int(n**0.5), 2) 中的

last

数字不是

n

的整数除数，会发生什么：

if n % x ==0:
    prime = False # not this
else:
    prime = True # this

因此 即使之前所有的检查都评估了

False

，你也称

n

为素数。要解决此问题，对代码进行的最小更改是：

prime = prime and True # or 'prime &= True'

因此，如果

prime

已经是

False

，那么它仍然是

False

。

但是，请记住，对于素数，如果这些检查中的 any 是

False

n

则不是素数。您可以使用它和 Python 的

and

和

all

（它们是惰性评估的，即一旦找到

False

，就不再继续检查）来更有效地实现：

def rand_prime():
    while True:
        p = randint(10000, 100000)
        if (r % 2 != 0 and
            all(p % n != 0 for n in range(3, int(((p ** 0.5) + 1), 2))):
            return p

为了获得更好的性能，请注意

randrange

包含

step

参数，就像

range

一样，因此您可以跳过所有偶数（绝对不是质数！）：

def rand_prime():
    while True:
        p = randrange(10001, 100000, 2)
        if all(p % n != 0 for n in range(3, int((p ** 0.5) + 1), 2)):
            return p

注意：在我看来，

sqrt(n)

（来自

math

）对于其他技术含量较低的读者来说比

n ** 0.5

更清晰（尽管它可能会也可能不会更高效）。

Answer 2

看一下选项卡：else 应该引用整个 for 循环，而不是 iF

def RandomPrime():
  prime = False
  while prime == False:
    n = random.randint(10000, 100000)
    if n % 2 != 0:
      for x in range(3, int(n**0.5), 2):
        if n % x ==0:
          break
      else:
          prime = True


  return n

Answer 3

您的代码中有错误：

1. 不正确的“else：”；如果余数不为 0，则不能声明该数为质数； 所有剩余都应该非零
2. int(n*0.5) 应为 int(n*0.5 + 1) 以防止舍入错误

可能的解决方案是

def RandomPrime():
  while True:
    n = random.randint(10000, 100000)

    if n % 2 == 0:
      continue;

    prime = True;

    for x in range(3, int(n**0.5 + 1), 2):
      if n % x == 0:
        prime = False;

        break; 

    if prime: 
      return n

Answer 4

正确的逻辑，您在设置

True

时

n % x

！ = 第一次

0

：

  for x in range(3, int(n**0.5), 2):
    if n % x ==0:
      prime = False
    else:
      prime = True

应该是：

  prime = False
  for x in range(3, int(n**0.5), 2):
    if n % x ==0:
      break
  else: 
    prime = True

阅读 break 和 continue 语句，以及 else 循环子句。

编写等效代码的较短方法是（来自@Steve Jesso）：

prime = all(n % x != 0 for x in range(3, int(n**0.5), 2)

Answer 5

一遍又一遍地生成大的随机数可能会花费大量时间。出于这个原因，我选择了一个随机数，然后递增它直到找到素数。

import random

def generate_big_prime(size:int):
    p = random.randrange(2 ** (size - 1), 2 ** size - 1)
    if p % 2 == 0:
        p += 1
    while not is_prime(p):
        p += 2
    return p

其中

size

是所需的位数，

is_prime(n:int)

是素性测试。

由于测试素性可能非常慢，特别是对于大数，我会推荐 Miller-Rabin 素性测试，因为它的效率。