在Python中,通常最好返回一个生成器,它将返回无限的质数序列,而不是列表。
ActiveState有一个旧版Eratosthenes筛法的列表recipes
这里是其中之一,使用itertools count更新到Python 2.7,并使用了步骤参数,这在原始配方编写时不存在:
import itertools as it
def sieve():
""" Generate an infinite sequence of prime numbers.
"""
yield 2
D = {}
for q in it.count(3, 2):
p = D.pop(q, 0)
if p:
x = q + p
while x in D: x += p
D[x] = p
else:
yield q
D[q*q] = 2*q
由于它是一个生成器,所以比生成整个列表更节省内存。由于它定位复合数,因此在计算上也更有效率。
运行此命令:
>>> g=sieve()
然后每个后续的调用都返回下一个质数:
>>> next(g)
2
>>> next(g)
3
你可以使用islice来获取在边界之间的列表(例如,从第一个质数到第X+Y个质数的列表……)。
>>> tgt=0
>>> tgt, list(it.islice(sieve(), tgt, tgt+10))
(0, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29])
>>> tgt=1000000
>>> tgt, list(it.islice(sieve(), tgt, tgt+10))
(1000000, [15485867, 15485917, 15485927, 15485933, 15485941, 15485959, 15485989, 15485993, 15486013, 15486041])
a = a + 1
可以简化为a += 1
。 - pygeek