Python中的惰性埃拉托斯特尼筛法

Question

我正在尝试用 Python 3.2 编写一个懒惰版的埃拉托斯特尼筛法。下面是我的代码：

import itertools
def primes():
    candidates = itertools.count(2)
    while True:
        prime = next(candidates)
        candidates = (i for i in candidates if i % prime)
        yield prime

但是，当我遍历 primes() 时，我只得到了连续的数字。例如，

print(list(itertools.islice(primes(),0,10)))

打印出的列表是

[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

让我惊讶的是，下面这个小小的修改让 primes() 正常工作了：

def primes():
    candidates = itertools.count(2)
    while True:
        prime = next(candidates)
        candidates = (i for i in candidates if i % prime)
        next(itertools.tee(candidates)[1]) ########### NEW LINE
        yield prime

我猜我对生成器参数的作用范围有些理解不清，

candidates = (i for i in candidates if i % prime)

但我看不出如何在不添加这个看起来随机的新行的情况下修复代码。有人知道我哪里出错了吗？谢谢。

Answer 1

这里有一个用Python写的真正的素数筛选算法，这个算法是根据一篇论文中的Haskell代码实现的，论文链接是：梅丽莎·E·奥尼尔的《真正的埃拉托斯特尼筛法》

这个算法不使用递归或者试除法，但它对内存的需求比较大。

from heapq import heappush, heappop, heapreplace
def sieve():
    w = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
    for p in [2,3,5,7]: yield p
    n,o = 11,0
    t = []
    l = len(w)
    p = n
    heappush(t, (p*p,n,o,p))
    yield p
    while True:
        n,o = n+w[o],(o+1)%l
        p = n
        if not t[0][0] <= p:
            heappush(t, (p*p,n,o,p))
            yield p
            continue
        while t[0][0] <= p:
            _,b,c,d = t[0]
            heapreplace(t, (b*d,b+w[c],(c+1)%l,d))

接下来：

import itertools
print list(itertools.islice(sieve(),0,10))

会输出：

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Answer 2

如果你担心变量的作用范围，可以创建对象或函数来帮你管理这些变量：

def filter_multiples(n, xs):
    for i in xs:
        if i % n
            yield i

def primes():
    candidates = itertools.count(2)
    while True:
        prime = next(candidates)
        candidates = filter_multiples(prime, candidates)
        yield prime

---

（我现在没有办法使用Python解释器，所以不确定这个方法最后是否真的有效……）

---

顺便说一下，你用的算法其实并不是真正的埃拉托斯特尼筛法。如果你有时间，可以看看这篇很不错的论文： http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Answer 3

解决办法其实就是把：

candidates = (i for i in candidates if i % prime)

换成：

candidates = (lambda prime: (i for i in candidates if i % prime))(prime)