素数生成を高速化するために、Python でエラトステネスのふるいアルゴリズムを最適化するにはどうすればよいでしょうか?

エラトステネスの篩 - Python での素数の検索

問題:

実装の試行中Python のエラトステネスのふるいアルゴリズムでは、実行速度が遅くなることがよくあります

解決策:

指定された実装には、いくつかの改善点があります:

1 。最適化されていないアルゴリズム:

• 初期実装の primes_sieve は素数のリストを維持するため、非効率的な要素の削除につながります。
• primes_sieve1 は素数フラグの辞書を使用しますが、適切な反復がありません。および冗長要素マーキング。

2.リスト操作の非効率性:

• Python リストから要素を削除すると、後続の要素をシフトする必要があるため、コストがかかる操作になります。

最適化された実装:

これらの問題を解決するには、次の最適化されたものを検討してください。実装:

def primes_sieve2(limit):
    a = [True] * limit
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

主な改善点:

• 素数フラグにリストを直接使用し、コストのかかるリストのサイズ変更を回避します。
• 遅延生成オンデマンドで素数を取得できるため、完全な素数を保存する必要がなくなります。 list.
• 素数の 2 乗から開始することにより、非素数因子を効率的にマークします。

以上が素数生成を高速化するために、Python でエラトステネスのふるいアルゴリズムを最適化するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。