2つの数字の間の素数を見つける高速アルゴリズム

Question

私の問題は、与えられた2つの数値の間の素数の数を減らすことに還元されます。1 to (1000)!のような大きな範囲を持つことができるので、数学的な最適化が必要です。

明らかにこの方法ではふるい法が遅すぎることが明らかです。適用できる数学的な最適化はありますか？たとえば、この大きな空間の小さな部分集合を取って残りの数についての推論を行うなどです。

P.S：私は行き詰まっているようですが、私が探しているのはこれを解決するのに役立つ最適化です。また、私はシングルスレッドのアプローチを探しています。

編集：私が考えていたことは、大きな素数に関連する多くの問題を解決することができます。誰かがグローバルな素数表を維持し、ルックアップに利用できるようにすることです。 PrimeGridプロジェクトの参加者は、このために役立ちます。

Answer 1

1000!（階乗）の高さになりたいからです。現在の技術で現在知られている方法で正確な結果を得ることはできません。

Prime Counting Functionは、10^24までのいくつかの値に対して正確に評価されています。あなたは1000!を打つことはできません。

---

しかし、あなたは大丈夫かもしれ近似値よりも言及しているので、あなたは総理カウント機能に近似としてLogarithmic Integralを使用することができます。

Prime Number Theoremに基づいています。プライムカウント関数は、対数積分に漸近しています。

Answer 2

私が知っている最も速い方法は、知られている非素数（偶数、範囲内の開始数よりも低い除数を持つすべての数）をできるだけ速く排除してから残りはEuclidean algorithmのようなものを使用して、その番号がプライムであるかどうかを判断します。

Answer 3

あなたがここにあなたのオプションを調査することができます http://en.wikipedia.org/wiki/Prime_counting_function

をこれも参考になります。あなたは1000年までにそれを必要とする理由 http://mathworld.wolfram.com/PrimeCountingFunction.html

は、私が問い合わせてもよいです！ ？誰もこれまで数え切れなかったように見えます。 1-10^23の1,925,320,391,606,803,968,923の素数があります。 1000！ = 10^120。私は今好奇心が強い。

Answer 4

与えられた境界より下の素数の数にはfast, simple approximationがあります。正確な値が必要ない場合は、この数式の2つの評価の差によって、近い将来得られるでしょう。

Answer 5

Lagariasなどが開発したプライムカウントアルゴリズムは、他の人が引用したように、O（n ^（2/3））で大まかに動作します。 k1からk2までの素数のふるいはおおよそO（max（sqrt（k2）、k2 - k1）を取るので、あなたの下限と上限はどれくらい離れているかチェックし、ふるいをかけるか、素数計算アルゴリズムより素早く速くなるであろう。素数カウントアルゴリズムは、それらを個々に数えるよりも、合理的に互いに近い様々な値nについて、1からnまでの素数を数えるように調整することができる。（基本的には、数Nを選択し、サイズn/Nのふるいを作成し、そのふるいでN^2の値を検索する.O（n ^（2/3））は、N = （1/3）の両方の演算はN ^（2/3）ステップをとるが、そのnは異なるnに対して再利用することができるが、異なる値を調べる必要がある。 （一度だけ）ふるいのコストを増加させるが、検索のコストを削減する（k回）。

約1000の場合、チャンスはありません。 nに小さな（ish）要素がない場合、[n、n]の素数の数をそのサイズの値で数えることさえできません。