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

修复实际上是将： 替换

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

为：

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

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

---

我现在无法访问 Pytho 解释器，所以我不知道这最终是否真的有效，或者不是...）

---

顺便说一句，您使用的算法并不是真正的埃拉斯托尼筛法。如果您有时间，请查看这篇很酷的论文：http:// /www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Answer 3

下面是基于论文中的 haskell 代码的真正素数筛的 Python 实现： The Genuine Sieve of Eratosthenes by Melissa E. O'Neill

它不使用递归或试除法，但相当消耗内存。

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]