ホームページ >バックエンド開発 >Python チュートリアル >与えられた整数 N より小さいすべての素数を生成する最速のアルゴリズムは何ですか?
与えられた整数 N より小さいすべての素数を生成する最速のアルゴリズムは何ですか?
- DDDオリジナル
- 2024-12-18 02:35:10627ブラウズ
N 以下の素数をすべてリストする最速の方法: 探索
問題:
すべてをリストする最速の方法を決定する指定された整数より小さい素数N.
質問:
指定されたアルゴリズムを最適化して実行を高速化できますか?
答え:
提供されたアルゴリズムは速度を大幅に向上させることができます。さまざまな実装を比較すると、Psyco を使用した rwh_primes1 が 1,000,000 未満の素数を生成するのに最も効率的であることがわかります。
追加の調査結果:
- Psyco を使用しないと、rwh_primes2 が出現します。最速として
- NumPy を利用すると、テストされたすべてのメソッドの中で primesfrom2to が最速であることが証明され、パフォーマンスがさらに向上します。
実装の詳細:
- ambi_sieve_plain: 単純な sieve ベース
- rwh_primes、rwh_primes1、および rwh_primes2: Robert William Hanks のアルゴリズムのバリエーション。
- sieve_wheel_30: 30 ベースの計算用に最適化された特殊なアルゴリズム。
- sieveOfEratosthenes:古典的なふるい法
- sieveOfAtkin: モジュロ演算を利用した最新のふるい。
- sundaram3: より小さい数値のセットを最適化した Sundaram のアルゴリズム。
- ambi_sieve: ふるいベースのアプローチNumPyを使って最適化。
- primesfrom3to および primesfrom2to: 素数を効率的に生成するための NumPy ベースのアルゴリズム。
タイミング:
| メソッド | 時間 (ミリ秒) Psyco | なしの時間 (ミリ秒)サイコ | ||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| rwh_primes1 | 43.0 | 93.7 | ||||||||||||||||||||||||||||||||||||
| sieveOfAtkin | 46.4 | 314.0 | ||||||||||||||||||||||||||||||||||||
| rwh_primes | 57 .4 | 94.6 | ||||||||||||||||||||||||||||||||||||
| sieve_wheel_30 | 63.0 | 97.4 | rwh_primes2 | 67.8 | 68.1 | |||||||||||||||||||||||||||||||||
| エラトステネスのふるい | 147.0178.0 | |||||||||||||||||||||||||||||||||||||
| ambi_sieve_plain | 152.0 | 286.0 | ||||||||||||||||||||||||||||||||||||
| sundaram3 | 194.0 | 416.0 | ||||||||||||||||||||||||||||||||||||
| primesfrom2to |
|
N/A | ||||||||||||||||||||||||||||||||||||
| primesfrom3to | 18.4 | 該当なし | ||||||||||||||||||||||||||||||||||||
| ambi_sieve | 29.3 | 該当なし |
以上が与えられた整数 N より小さいすべての素数を生成する最速のアルゴリズムは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
声明：
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。