nより小さいすべての素数を報告する

Question

与えられた数nより小さいすべての素数を出力する必要があります。私はEratothenesのふるいを使うことができますが、そのアルゴリズムの実行時間はO（n）ではありません。この問題のO（n）時間解決はありますか？

Answer 1

任意の数字をO（n）時間の複雑さの素数としてチェックするアルゴリズムはありません。私はNSA（および暗号問題を扱う他の組織）がそれほど満足できないと確信しています:-)

O（n）以上の方法は、最初の5000万の素数を事前に計算し（またはsomeone else's already-precalculated listを使用）、それをルックアップとして使用します。私はそのようなファイルをローカルに持っていて、番号がプライムかどうかを確認するためにgrepを実行するのは簡単なことです。それは任意の数字には役立ちませんが、私はそれほど大きなものを使う必要はほとんどありません。もちろん、暗号の人はその目的のためにそのようなリストを消滅させることはほとんどないと考えています。

ビットマップ（最初の50万の素数は約120M）にすると、数字をバイトオフセットに変換するだけで複雑さをO（1）に減らすことさえできます。ビットシフトおよび/またはビット演算の2つが含まれる。

ただし、以下の素数のリストをある程度nにすることは、確かにO（n）時間の複雑さで実行可能です。

我々はO(N/log(log(N)))追加を使用してNまでの素数を計算するアルゴリズムを導入...

わずか実際にはO（n）よりも優れて次のとおりです。Sieve of Atkin主張を詳述Atkin and Bernstein paper。

しかし、まだルックアップソリューションと競合する可能性は低いです。私のアドバイスは、AtkinやEratosthenesを使ってリストを作ることです。実際にはこのビットをのように実行するだけなので、パフォーマンスは重要ではありません。

次に、素数をチェックするためにリスト自体を使用します。

Answer 2

実装は難しくなりますが、Sieve of Atkinはより複雑です。

Answer 3

エラトステネスの篩は、時間複雑さO（n log log n）を有する。関数log log nの成長は非常に遅くなります。つまり、log（log（10^9））= 3となります。つまり、時間の複雑さの一部を定数として扱い、それを無視して時間の複雑さを「ほぼ」O（n） 。

時間O（n）またはO（n/log log n）で動作する様々なアルゴリズムがあります.PritchardのホイールふるいとAtkinsのふるいを含みます。しかし、一定の要因によって、一般に、エラトステネス篩よりも実際にはアルゴリズムの速度が遅くなります。あなたが極端なスピードを必要としない限り、あなたが何をしているのかを知っていて、それをやるのに多くの時間を費やしたいなら、実用的な答えはエラトステネスのふるいです。

あなたの質問には、素数のリストを印刷するつもりです。その場合、出力は選択したアルゴリズムの実行時間を支配します。だから自分自身に好意を持ち、シンプルなエラトステネス篩を実装してください。