在 python 中实施 "Sieve of Eratosthenes" 时出现麻烦的过滤器行为

Question

我为 "Sieve of Eratosthenes" 的 试验部门 变体想出了这个 Python 代码：

import itertools

def sieve():
    # begin with all natural numbers above 1
    picker = itertools.count(2)
    while True:
        # take the next available number
        v = next(picker)
        yield v
        # filter from the generator its multiples
        picker = filter(lambda x: x % v != 0, picker)

它没有像我预期的那样工作。

在调试它时，我得到一些行为，当 filter 被调用时我不明白：lambda 的 x 参数得到一个具体的参数，它是 [=19 的下一个元素=] 发电机。即使在查看 filter.

的文档后，我也不明白这种行为

运行

s = sieve()
for i in range(5):
    print(next(s))

我得到：

而不是

更新：

我的错误来自于对 lambda 在 Python 中的工作方式的误解，更多关于 here。

向 lambda 添加一个额外的参数修复了这个问题：

picker = filter(lambda x, prime = v: x % prime != 0, picker)

Answer 1

我认为问题是因为您依赖于局部变量，而您创建的生成器（使用 filter()）正在引用局部变量，当生成器继续迭代时这些变量将被覆盖。

如果您改为使用本地函数，则效果很好：

def sieve():
    def selector(iterator, d):
        for x in iterator:
            if x % d != 0:
                yield x
    picker = itertools.count(2)
    while True:
        # take the next available number
        prime = next(picker)
        yield prime
        # filter from the generator its multiples
        picker = selector(picker, prime)

尝试 list(itertools.islice(sieve(), 10)) 显示：

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

但我真的需要指出，这是一个纯粹的教育解决方案，用于展示事物的工作原理。我不建议将此解决方案用于任何生产代码。它在内部建立了大量的生成器，只有当你放下父生成器的句柄时，这些生成器才会被释放。这可能是一种资源浪费，您可以创建无限数量的素数，而无需创建无限数量的生成器。

在 python 中实施 "Sieve of Eratosthenes" 时出现麻烦的过滤器行为

Troublesome filter behavior when implementing the "Sieve of Eratosthenes" in python

python

algorithm

primes

python-3.x