使用 Python 处理大素数的有效方法是什么？你在这里或谷歌上搜索，你会发现很多不同的方法……筛子、素数测试算法……哪些方法适用于更大的素数？
问问题
9715 次
3 回答
11
为了确定一个数字是否是素数，有筛子和素数测试。
# for large numbers, xrange will throw an error.
# OverflowError: Python int too large to convert to C long
# to get over this:
def mrange(start, stop, step):
while start < stop:
yield start
start += step
# benchmarked on an old single-core system with 2GB RAM.
from math import sqrt
def is_prime(num):
if num == 2:
return True
if (num < 2) or (num % 2 == 0):
return False
return all(num % i for i in mrange(3, int(sqrt(num)) + 1, 2))
# benchmark is_prime(100**10-1) using mrange
# 10000 calls, 53191 per second.
# 60006 function calls in 0.190 seconds.
这似乎是最快的。你看到的还有另一个版本not any，
def is_prime(num)
# ...
return not any(num % i == 0 for i in mrange(3, int(sqrt(num)) + 1, 2))
然而，在基准测试中，我克服70006 function calls in 0.272 seconds.了使用all 60006 function calls in 0.190 seconds.while testing if 100**10-1was prime。
如果您需要找到下一个最高质数，则此方法不适合您。您需要进行素数测试，我发现Miller-Rabin算法是一个不错的选择。费马方法稍微慢一些，但对伪素数更准确。在这个系统上使用上述方法需要 +5 分钟。
Miller-Rabin算法：
from random import randrange
def is_prime(n, k=10):
if n == 2:
return True
if not n & 1:
return False
def check(a, s, d, n):
x = pow(a, d, n)
if x == 1:
return True
for i in xrange(s - 1):
if x == n - 1:
return True
x = pow(x, 2, n)
return x == n - 1
s = 0
d = n - 1
while d % 2 == 0:
d >>= 1
s += 1
for i in xrange(k):
a = randrange(2, n - 1)
if not check(a, s, d, n):
return False
return True
Fermat算法：
def is_prime(num):
if num == 2:
return True
if not num & 1:
return False
return pow(2, num-1, num) == 1
要获得下一个最高质数：
def next_prime(num):
if (not num & 1) and (num != 2):
num += 1
if is_prime(num):
num += 2
while True:
if is_prime(num):
break
num += 2
return num
print next_prime(100**10-1) # returns `100000000000000000039`
# benchmark next_prime(100**10-1) using Miller-Rabin algorithm.
1000 calls, 337 per second.
258669 function calls in 2.971 seconds
使用Fermat测试，我们得到了 的基准45006 function calls in 0.885 seconds.，但您运行伪素数的机会更高。
所以，如果只需要检查一个数字是否是素数，第一种方法is_prime就可以了。如果您使用该mrange方法，它是最快的。
理想情况下，您希望存储由它生成的素数next_prime并从中读取。
例如，next_prime与Miller-Rabin算法一起使用：
print next_prime(10^301)
# prints in 2.9s on the old single-core system, opposed to fermat's 2.8s
1000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000531
您将无法return all(num % i for i in mrange(3, int(sqrt(num)) + 1, 2))及时执行此操作。我什至不能在这个旧系统上做到这一点。
为了确保next_prime(10^301)并Miller-Rabin产生正确的值，还使用Fermat和Solovay-Strassen算法对其进行了测试。
请参阅：gist.github.com上的fermat.py、miller_rabin.py和solovay_strassen.py
编辑：修复了一个错误next_prime
于 2013-06-25T13:04:57.313 回答
0
为了应对可能的不准确性，我对两种不同的呼叫math.sqrt执行方法进行了基准测试。来自这篇文章和这段 C 代码isqrt(n)isqrt_2(n)
最常见的方法：
def isqrt_1(n):
x = n
while True:
y = (n // x + x) // 2
if x <= y:
return x
x = y
cProfile.run('isqrt_2(10**308)')
基准测试结果：
isqrt_1 at 10000 iterations: 12.25
Can perform 816 calls per second.
10006 function calls in 12.904 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 12.904 12.904 <string>:1(<module>)
1 0.690 0.690 12.904 12.904 math.py:10(func)
10000 12.213 0.001 12.213 0.001 math.py:24(isqrt_1)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 0.000 0.000 {range}
2 0.000 0.000 0.000 0.000 {time.time}
这种方法非常慢。所以我们尝试下一个方法：
def isqrt_2(n):
if n < 0:
raise ValueError('Square root is not defined for negative numbers.')
x = int(n)
if x == 0:
return 0
a, b = divmod(x.bit_length(), 2)
n = 2 ** (a + b)
while True:
y = (n + x // n) >> 1
if y >= n:
return n
n = y
cProfile.run('isqrt_2(10**308)')
基准测试结果：
isqrt_2 at 10000 iterations: 0.391000032425
Can perform 25575 calls per second.
30006 function calls in 1.059 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 1.059 1.059 <string>:1(<module>)
1 0.687 0.687 1.059 1.059 math.py:10(func)
10000 0.348 0.000 0.372 0.000 math.py:34(isqrt_2)
10000 0.013 0.000 0.013 0.000 {divmod}
10000 0.011 0.000 0.011 0.000 {method 'bit_length' of 'long' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 0.000 0.000 {range}
2 0.000 0.000 0.000 0.000 {time.time}
如您所见， 和 的差异isqrt_1(n)是isqrt_2(n)惊人的11.858999967575 seconds快。
您可以在 Ideone.com 上查看此操作或获取代码
注意：Ideone.com 导致执行超时，isqrt_1(n)因此基准降低到10**200
于 2013-06-27T19:30:16.053 回答
0
我已经写了两篇关于这方面的文章，以及基准测试，看看哪些方法更快。
使用 PythonBaillie-PSW编写素数是在素数测试知识之前编写的。
之后编写了带有 Python v2Lucas pseudoprimes的素数，对素数和Baillie-PSW素数测试进行了基准测试。
于 2013-06-27T16:06:28.640 回答