python - Python中的素数生成器

Question

我尝试使用 Eratosthenes 的史蒂夫在 Python 中创建所有素数的流。但是，我收到一个错误。

这是我尝试过的:

def genPrimes0(N):
    if (isPrime(N)):
        yield [N]
        filter(lambda x: N%x[0] == 0, genPrimes0(N+1))
    else:
        genPrimes0(N+1)


P = genPrimes0(2)

这是控制台:

>>> ================================ RESTART ================================
>>> 
>>> P.next()
[2]
>>> P.next()

Traceback (most recent call last):
  File "<pyshell#10>", line 1, in <module>
    P.next()
StopIteration
>>> 

有什么想法吗？

编辑:

我想要递归。我想使用 LAZY 评估进行实验。对这个问题不是特别感兴趣，而是对惰性评估感兴趣——我完全随机地选择了这个问题来进行实验。

我在 Idle 中使用 Python 2.7，但这并不重要。了解发生了什么很重要。

Answer 1

我认为您在当前的生成器中过于努力。您可以做更少的工作(例如，拥有一个 isPrime oracle)并让算法完成它的工作:

def primes(n=2): # don't provide a different n value, or you will get odd results
    yield n
    yield from filter(lambda x: x % n, primes(n+1))

它使用了一些 Python 3.3 特定的语法(yield from)，但是您可以为早期版本做一个等价的生成器，只需让它在过滤器的结果上显式循环即可。 @icktoofay 的回答显示了这种循环(他还指出 filter 只是 Python 3 中的生成器，所以如果您使用的是 Python 2，请使用 itertools.ifilter ).

示例输出:

>>> for p in primes():
    print(p)
    if p > 100:
        break


2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101