2

我尝试使用 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，但这并不重要。了解会发生什么很重要。

4

3 回答 3

6

我认为您在当前的生成器中太努力了。您可以少做很多工作（例如拥有一个isPrime预言机）并让算法做它的事情：

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))

yield from这使用了一些Python 3.3 特定的语法（@icktoofay 的回答显示了这种循环（他还指出这filter只是 Python 3 中的生成器，所以itertools.ifilter如果您使用的是 Python 2，请使用）。

示例输出：

>>> 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
于 2012-11-15T03:35:16.863 回答
4

您不需要递归进行惰性求值，您可以使用 itertools 中的函数来惰性计算素数。

import itertools    

def primes():
    numbers = itertools.count(2)
    while True:
        p = numbers.next()
        numbers = itertools.ifilter(lambda x, p=p: x%p, numbers)
        yield p

print list(itertools.islice(primes(), 100))
于 2012-11-15T03:39:22.350 回答
2

这不是 Eratosthenes，而是 som 非尾递归函数女巫只是填充堆栈。如果你有 isPrime 函数，你应该这样写

def gen_primes(start):
   return itertools.filter(isPrime , itertools.count(start) )
于 2012-11-15T03:08:50.653 回答