実現可能なプライムカウント関数の実装

Question

prime-counting function実装の計算可能な擬似コードを誰でも提供できますか？私は最初にHardy-Wright algorithmをコーディングしようとしましたが、その階乗は悲惨なオーバーフローを発生させ始めました。私は実用的なソリューションのためにGoogleを精査したが、せいぜい、従来のプログラムでは実現しなかった非常に難解な数学を発見した。

Answer 1

prime-counting関数pi（x）は、xを超えない素数の数を計算し、何世紀にもわたって数学者を魅了しました。 Adrien-Marie Legendreは18世紀の初めに、補助関数phi（x、a）を使って数式を与えました。これは最初の素数でふるい落とされないx以下の数を数えます。例えば、番号1,7,11,13,17,19,23,29,31,37,41,43,47および49の場合、φ（50,3）= 14である.φ関数は、φ （x、1）は、xを超えない奇数の数であり、P（a）は、 a番目の素数（P（1）= 2から数えて）です。

function phi(x, a) 
    if (phi(x, a) is in cache) 
    return phi(x, a) from cache 
    if (a == 1) 
    return (x + 1) // 2 
    t := phi(x, a-1) - phi(x // p[a], a-1) 
    insert phi(x, a) = t in cache 
    return t 

配列P店小さなするA番目の素数を、ふるい分けすることによって計算します。キャッシュは重要です。これがなければ、実行時間は指数関数的になります。与えられたφをとると、ルジャンドルの素数計算式は、a = pi（floor（sqrt（x）））であり、pi（x）=φi（x、a）+ a-1である。 Legendreはpi（10^6）を計算するために彼の公式を使用しましたが、78498という正解の代わりに78526を報告しました。これは、間違っていますが、手作業の複雑な計算では驚くほど近かったです。 1950年代

は、デリックH.レーマーはカウント素数のための改良されたアルゴリズムを与えた：あっても、これらのアルゴリズムと

例えば

function pi(x) 
    if (x < limit) return count(primes(x)) 
    a := pi(root(x, 4)) # fourth root of x 
    b := pi(root(x, 2)) # square root of x 
    c := pi(root(x, 3)) # cube root of x 
    sum := phi(x,a) + (b+a-2) * (b-a+1)/2 
    for i from a+1 to b 
    w := n/p[i] 
    lim := pi(sqrt(w)) 
    sum := sum - pi(w) 
    if (i <= c) 
     for j from i to lim 
     sum := sum - pi(w/p[j]) + j - 1 
    return sum 

、PI（10^12）= 37607912018.、およびそれらの近代的変異体、及び非常に高速のコンピュータでは、piの大きな値を計算するのはやめても面倒です。この書面では、最も大きな既知の値はpi（10^24）= 18435599767349200867866です。

n番目の素数を計算するためにこのアルゴリズムを使用するには、素数定理の帰結はn番目の素数P ）はn> 5のn log nとn（log n + log log n）の間にあるので、境界でpiを計算し、二分法を使ってn番目の素数を決定し、境界が近いときにふるいに切り替える。

my blogにいくつかのエントリで素数について議論します。

Answer 2

ウィキペディアも役に立ちます。 prime countingの記事には、いくつかのポインタが含まれています。まず、すべての素数を生成しない最も単純なアルゴリズムの1つである「π（x）を評価するためのアルゴリズム」の項のMeisselによるアルゴリズムをお勧めします。

また、PomeranceとCrandallの本"Prime numbers a computational perspective"が役に立ちました。この本は、素数カウント方法の詳細で非常に使いやすい説明をしています。しかし、その性質上の話題は読者のほとんどにとってはあまりにも進んでいることを覚えておいてください。