这是我能想到的最好的算法。
def get_primes(n):
numbers = set(range(n, 1, -1))
primes = []
while numbers:
p = numbers.pop()
primes.append(p)
numbers.difference_update(set(range(p*2, n+1, p)))
return primes
>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import get_primes').timeit(1)
1.1499958793645562
可以做得更快吗?
这段代码有一个缺陷:因为 numbers
是一个无序集,所以不能保证 numbers.pop()
会从集合中删除最小的数字。尽管如此,它对某些输入数字有效(至少对我而言):
>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True
原文由 jbochi 发布,翻译遵循 CC BY-SA 4.0 许可协议
警告:
timeit
结果可能因硬件或 Python 版本的不同而有所不同。下面是一个比较多种实现的脚本:
非常感谢 stephan 让我注意到 sieve_wheel_30。感谢 Robert William Hanks 的 primesfrom2to、primesfrom3to、rwh_primes、rwh_primes1 和 rwh_primes2。
在 使用 psyco 测试的普通 Python 方法中,对于 n=1000000, rwh_primes1 是测试最快的。
在测试的普通 Python 方法中, 没有 psyco ,对于 n=1000000, rwh_primes2 是最快的。
在所有测试的方法中, 允许 numpy ,对于 n=1000000, primesfrom2to 是测试最快的。
使用以下命令测量时间:
用
{method}
替换为每个方法名称。素数.py:
运行脚本测试所有实现都给出相同的结果。