Python で素数の無限ストリームを効率的に生成するには?

Python で素数の効率的な無限生成器を実装するにはどうすればよいですか?

素数の無限系列を生成する効率的な方法は、エラトステネスの篩を使用することです。これは、非素数の倍数を繰り返しマークすることで非素数を削除します。この方法は効果的ですが、マークされた数値を保存するには大量のメモリが必要です。

erat2

これは、Python の標準ライブラリのクックブックにあるerat2 関数です。無限の素数系列を生成するために使用されます数値:

import itertools as it
def erat2( ):
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            # old code here:
            # x = p + q
            # while x in D or not (x&1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

erat2a

erat2 関数は、不必要なチェックを回避することでさらに最適化できます:

import itertools as it
def erat2a( ):
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            # old code here:
            # x = p + q
            # while x in D or not (x&1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

erat3

パフォーマンスをさらに高速化するには、erat3 関数を使用しますこれは、すべての素数 (2、3、および 5 を除く) の 30 を法とする結果が 8 つの特定の数値のみになるという事実を利用しています。これにより、ふるい分けプロセス中に必要なチェックの数が大幅に減少します。

import itertools as it
def erat3( ):
    D = { 9: 3, 25: 5 }
    yield 2
    yield 3
    yield 5
    MASK= 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0,
    MODULOS= frozenset( (1, 7, 11, 13, 17, 19, 23, 29) )

    for q in it.compress(
            it.islice(it.count(7), 0, None, 2),
            it.cycle(MASK)):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            x = q + 2*p
            while x in D or (x%30) not in MODULOS:
                x += 2*p
            D[x] = p

これらの最適化により、特に大きな素数を生成する場合にパフォーマンスが大幅に向上します。

以上がPython で素数の無限ストリームを効率的に生成するには?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。