与えられた整数 N より小さいすべての素数を生成する最速のアルゴリズムは何ですか?

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 ベースのアルゴリズム。

タイミング:

147.0テーブル>

メソッド

時間 (ミリ秒) 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

エラトステネスのふるい

178.0

ambi_sieve_plain

152.0

286.0

sundaram3

194.0

416.0

primesfrom2to

Method	Time (ms) with Psyco	Time (ms) without 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
sieveOfEratosthenes	147.0	178.0
ambi_sieve_plain	152.0	286.0
sundaram3	194.0	416.0
primesfrom2to	15.9	N/A
primesfrom3to	18.4	N/A
ambi_sieve	29.3	N/A

15.9

N/A

primesfrom3to

18.4

該当なし

ambi_sieve

29.3

該当なし

以上が与えられた整数 N より小さいすべての素数を生成する最速のアルゴリズムは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。