使用生成器的python中的质数

Question

我正在尝试用python编写一个程序来生成质数，使用的逻辑类似于在Haskell中编写质数程序时使用的逻辑(可以在他们的网站顶部找到)。我已经编写了以下两个生成器函数。

def integers():
    i=2
    while True:
        yield i
        i+=1

def primes(li):
    x=li
    while True:
        i=next(x)
        y=(j for j in x if %i!=0)
        yield i
        x=y

整数是数字2，3，4，5的生成器...所以我的猜测是

a=primes(integers())

应该给出质数的生成器，但它没有给出这类生成器。这是我得到的输出。

>>> next(a)
2
>>> next(a)
3
>>> next(a)
4
>>> next(a)
5
>>> next(a)
6

有什么建议吗？

Answer 1

在通常避免递归的Python中，您不会使用这种方法。但在itertools的帮助下，这里有一个在某种程度上等效的实现

>>> from itertools import count, chain
>>> def filter_primes(integers):
...     p = next(integers)
...     yield from chain([p], filter_primes(x for x in integers if x%p !=0))
...
>>> primes = filter_primes(count(2))
>>> next(primes)
2
>>> next(primes)
3
>>> next(primes)
5
>>> next(primes)
7
>>> next(primes)
11
>>> next(primes)
13
>>> next(primes)
17
>>> next(primes)
19
>>> next(primes)
23
>>> next(primes)
29

使用more itertools help获取前20条：

>>> primes = filter_primes(count(2))
>>> list(islice(primes, 20))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
>>>

Answer 2

您的代码看起来很合理。它不起作用是因为它做了一个令人惊讶的错误的假设:生成器表达式关闭了它使用的值。

相反，(j for j in x if j % i != 0)不会通过i关闭！这就是在执行过程中稍后更改i会更改过滤表达式的原因。与针对连续素数构建一堆过滤器不同，整个生成器链在每一步都会发生变化，以过滤最后生成的值。

演示：

>>> v = 1
>>> gen = (x for x in itertools.count() if x % v == 0)
>>> print next(gen), next(gen), next(gen)
0 1 2
>>> v = 3
>>> print next(gen), next(gen), next(gen)
3 6 9

递归解决方案是修复它的一种显而易见的方法。

另一种方法是使用执行闭包的lambda (参见IIFE)：

def primes(source):
    while True:
        value = next(source)
        yield value
        source = (lambda v: (j for j in source if j % v != 0))(value)

这是可行的，但它产生的开销与简单的递归几乎相同，而且读起来更糟。不过，它不会占用调用堆栈。