python - 在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。

但是，请记住，对于素数，如果这些检查中任何为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(尽管它是 may or may not be more efficient )。