生成10^300到10^301之间随机质数的Python应用

Question

我需要做一个Python应用程序，生成一个在10的300次方和10的301次方之间的随机质数。我用这个方法实现了，但速度很慢。有没有什么解决办法？

import random , math
check_prime = 0

print "请稍等 ..."

def is_prime(n):

import math

n = abs(n)

i = 2

while i <= math.sqrt(n):

if n % i == 0:

return False

i += 1

return True

while check_prime == 0 :

randomnumber = random.randrange(math.pow(10,300),math.pow(10,301)-1)

if is_prime(randomnumber):

print randomnumber

break

Answer 1

正如评论中所说的，你可以忘记在10^300和10^301之间列出所有的质数，然后随机挑一个——这个范围内的质数数量实在是太多了，根本不可能这样做。

从我看来，唯一可行的方法就是随机选一个数字，然后测试它是否是质数。如果不是，就再选一个，直到找到一个质数为止。

关于质数测试，这本身就是一个很大的话题（已经有很多相关的库和书籍）。基本上，你首先会进行一些快速测试，排除那些显然不是质数的数字，然后再用一些常见的质数测试方法（比如米勒-拉宾测试、AKS测试等）。我对这些方法了解不够，无法推荐具体的一个，但这确实是个需要研究的数学话题，所以你可以去看看 https://math.stackexchange.com/。

例如，你可以参考这个问题，里面有一些简单的做法：

如何判断一个数字是质数还是合成数？

关于你的代码：

你发布的代码基本上就是我刚才描述的那样，不过它使用了一种非常简单的质数测试方法（对所有1到sqrt(n)的数字进行试除）。这就是它运行得这么慢的原因。如果你使用更好的质数测试方法，速度会快很多。

Answer 2

首先，别用 math.pow()，因为它只是一个包装器，实际上是调用了 C 语言中的浮点数函数，而你的数字太大了，浮点数无法准确表示。建议使用 Python 的幂运算符，也就是 **。

其次，如果你使用的平台上有 gmpy 的版本，建议用它来进行质数测试。

最后，正如 eumiro 提到的，你可能面临的问题规模太大，可能没有真正快速的解决方案。

Answer 3

如果你需要一个简单快速的方法，可以直接用费马小定理。

def isPrime(p):
    if(p==2): return True
    if(not(p&1)): return False
    return pow(2,p-1,p)==1

虽然这个方法对于随机数效果不错，但对于一些叫做“伪素数”的数字就不太管用了。（这种数字比较少见）不过，如果你想要一个更可靠、实现起来也简单的方法，我建议你去了解一下米勒-拉宾素性测试。

顺便说一下：在Python中，pow(a,b,c)这个函数的运行时间是O(log(b))。