Python で効率的に素数を生成するためにエラトステネスのふるいを最適化するにはどうすればよいでしょうか?

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

エラトステネスのふるいは、素数を見つけるための古典的なアルゴリズムです。ただし、パフォーマンスのボトルネックを回避するには、正しく実装することが重要です。

元の実装

提供された primes_sieve 関数は、候補素数のリストを維持し、非素数を繰り返し削除します。リストを調べて因数を削除することで素数を決定します。このアプローチは、リスト操作のコストが高いため、本質的に非効率です。

辞書ベースの最適化

改良された primes_sieve1 関数は、辞書を使用して素数フラグを格納します。リストベースのアプローチよりも高速ではありますが、依然として課題に直面しています。未定義の順序で辞書を反復処理するため、非素因数の冗長なマーク付けが発生します。さらに、最終的な辞書をリストに変換するため、不要なオーバーヘッドが発生します。

正しく効率的な実装

正しいエラトステネスのふるいアルゴリズムは、ブール フラグのリストを利用して、素数性を示します。 primes_sieve2 関数は、すべての数値のフラグを True に初期化し、0 と 1 のフラグを False に設定します。リストを反復処理し、フラグを False に設定して素数以外をマークします。

このアプローチは次の理由から効率的です。

• 辞書の代わりにリストを使用し、オーバーヘッドを回避します。
• 素因数のみを非素数としてマークし、冗長性を削減します。
• 各素数の 2 倍ではなく 2 乗から開始することで、マーキング プロセスを最適化します。

エラトステネスのふるいを正しく実装することで、パフォーマンスを大幅に向上させることができます。素数の生成により、200 万未満の素数を見つけるなどの大きな入力制限にも適しています。

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