2

エラトステネスのスティーブを使用して、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評価を使って実験したいです。特に問題には興味がありませんが、遅延評価については、実験を行うためにこの問題を完全にランダムに選択しました。

アイドル状態でPython2.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))

これは Python 3.3 固有の構文 ( yield from) を使用しますが、フィルターの結果に対して明示的なループを作成するだけで、以前のバージョンの同等のジェネレーターを実行できます。@icktoofayの回答は、そのようなループを示しています（またfilter、Python 3のジェネレーターにすぎないことも指摘しているため、itertools.ifilterPython 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ではありませんが、末尾再帰関数ではない魔女がスタックを埋めるだけです。isPrime 関数がある場合は、次のように書く必要があります

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