2

エラトステネスのふるいアルゴリズムを使用して素数ジェネレーターを実装しようとしています。再帰的イテレータのマージを使用してsifterを実装してみるだけです。

私がしていることはこれです：

from itertools import count,islice,groupby
from heapq import merge


def primes3():
    p = 2
    yield p
    sifter = (i*p for i in count(p))
    s = next(sifter)
    for p in count(p+1):
        if p==s: # this p is sieved out
            print('s: {}'.format(s))
            s = next(sifter)
        else:
            yield p # this is prime
            print('p: {}'.format(p))
            sifter = (k for k, g in groupby(merge(sifter,(i*p for i in count(p))))) #add this serie to the sifter: p*p, p*(p+1), p*(p+2), ...


print(list(islice(primes3(),10)))

出力は次のとおりです。

p: 3
s: 4
p: 5
p: 6
p: 7
p: 8
p: 9
p: 10
p: 11
s: 12
[2, 3, 5, 6, 7, 8, 9, 10, 11, 13]

ふるいにかけられる最初の数は4です。しかし、次は12、6あるべき姿ではありません。何故ですか？次のコードで確認しました。

>>> sifter = (i*2 for i in count(2))
>>> next(sifter)
4
>>> sifter = (k for k, g in groupby(merge(sifter,(i*3 for i in count(3)))))
>>> print(list(islice(sifter,20)))
[6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 28, 30, 32, 33, 34]

したがって、ご覧のとおり、テスト条件では、sifterによって正しい結果が得られます。

どこを間違えているのですか？見た目がないのは些細なことだと思います。

4

1 に答える 1

2

私は同意する必要があります、このようなものは時々非常に混乱する可能性があります（しかし素晴らしいパズルです！）。

sifter値が変更されるとイテレータが変更されることがわかりpます（ちなみに、これをテストするためにpython3ではなくpython2.6.5を使用しているため、印刷構文は少し異なります）：

>> p = 2
>> sifter = (i*p for i in count(p))
>> for x in range(3):
>>    print next(sifter)
4
6
8
>>> # now lets see what happens when we change p
>>> p = 3
>>> for x in range(3):
>>>     print next(sifter)
15
18
21

したがって、i*pイテレータの部分は、pが更新されるとすぐに、新しいpで評価されます。pは実際にメインループで更新されます。そのため、期待した結果が得られません。

これを解決する簡単な方法があります。イテレータがpに制限されないように、sifterイテレータを生成する関数を作成します。

def gensifter(x):
    return (i*x for i in count(x))

これをコードに入れます（ここでも、Python 2.6.5に変換しました）：

def primes3():
    p = 2
    yield p
    sifter = gensifter(p) # <-- changed!
    s = next(sifter)
    for p in count(p+1):
        #print '(testing p = %d\ts = %d)' % (p, s)
        if p==s: # this p is sieved out
            print 's:', s
            s = next(sifter)
        else:
            yield p # this is prime
            print 'p:', p
            sifter = (k for k, g in groupby(merge(sifter,gensifter(p)))) # <-- changed!

今すぐ結果を見てみましょう：

>>> print list(islice(primes3(), 10))
p: 3
s: 4
p: 5
s: 6
p: 7
s: 8
s: 9
s: 10
p: 11
s: 12
p: 13
s: 14
s: 15
s: 16
p: 17
s: 18
p: 19
s: 20
s: 21
s: 22
p: 23
s: 24
s: 25
s: 26
s: 27
s: 28
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

プライムナンバーが豊富！

于 2012-08-23T16:49:04.633 に答える