Python 应用程序生成 10^300 和 10^301 之间的随机素数

Question

我需要让 Python 应用程序生成一个介于 10^300 和 10^301 之间的随机素数，我用这个完成了，但是速度很慢。有什么解决办法吗？

import random , math
check_prime = 0<p></p>

<p>print "Please wait ..."
def is_prime(n):
    import math
    n = abs(n)
    i = 2
    while i <= math.sqrt(n):
        if n % i == 0:
            return False
        i += 1<br/>
    return True</p>

<p>while check_prime == 0 :
    randomnumber = random.randrange(math.pow(10,300),math.pow(10,301)-1)
    if is_prime(randomnumber):
        print randomnumber
        break
</p>

Answer 1

首先要注意的是:不要使用 math.pow()，因为它只是 C 浮点函数的包装器，而且您的数字太大而无法准确表示为 float 。使用 Python 的求幂运算符，即 **。

第二:如果您使用的平台版本为 gmpy ，将其用于您的素数测试。

第三:正如 eumiro 指出的那样，您可能要处理的问题空间太大，以至于没有任何真正快速的解决方案。