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

エラトステネスのふるいの改善: Python 素数生成の最適化

エラトステネスのふるいは、事前定義された制限まで素数を見つけるための効率的なアルゴリズムです。ただし、単純な Python 実装では、制限が大きくなると過度に遅くなる可能性があります。

ボトルネックの特定

この例では、プロファイリングにより、要素を削除するのにかなりの時間が費やされていることが明らかになりました。リスト（素数）。この操作は、特に長いリストの場合、計算コストが高くなります。

リストを辞書で置き換える

この問題に対処するための最初の試みには、リストを辞書 (素数) で置き換えることが含まれていました。 。これにより、要素をより迅速に削除できるようになりました。しかし、このアルゴリズムには依然として次のような問題がありました。

• 未定義の順序での辞書の反復
• 非素数の因数の冗長マーク

正しいアルゴリズムを実装する

完全にアルゴリズムを最適化するため、修正が必要でした:

1. 素数フラグの辞書の代わりにリストを使用
2. 非素因数をスキップ
3. 因数マーキングを開始素数の 2 倍ではなく 2 乗

最適化されたアルゴリズム

最適化されたアルゴリズム (primes_sieve2) は、素数フラグのブール値のリストを使用します。 1 より大きいすべての数値についてリストを True に初期化します。次に、リストを反復処理して、素数以外の数値をマークします。

def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    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

これらの重要な側面を最適化することで、アルゴリズムはパフォーマンスを大幅に向上させ、数秒以内に最大 200 万までプライムされます。

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