17

n番目の素数の近似値を返す関数はありますか? これはおおよその逆素数カウント関数のようなものになると思います。たとえば、この関数に 25 を指定すると、約 100 の数値が返されます。または、この関数に 1000 を指定すると、約 8000 の数値が返されます。返される数値が素数かどうかは気にしませんが、それは高速です（したがって、 n番目を返すために最初のn個の素数を生成しません。）

ふるい（ EratosthenesまたはAtkin ）を使用して最初のn個の素数を生成できるように、これが欲しいです。したがって、n番目の近似は、理想的には実際のn番目の素数の値を過小評価することはありません。

(更新: n番目の素数の上限を見つける良い方法については、私の回答を参照してください。)

4

7 に答える 7

10

それらのすべての答えに感謝します。そのようなかなり単純なものがあるのではないかと疑っていましたが、その時は見つけられませんでした。私ももう少し調べてみました。

ふるいが最初のn個の素数を生成するようにしたいので、近似値がn番目の素数以上になるようにします。(したがって、 n番目の素数の上限が必要です。)

ウィキペディアは、次の上限を示していますn >= 6

p_n <= n log n + n log log n   (1)

ここp_nで、 はn番目の素数で、logは自然対数です。これは良いスタートですが、少なからず過大評価される可能性があります。The College Mathematics Journal のこの記事では、n >= 7022

p_n <= n log n + n (log log n - 0.9385)   (2)

次の表が示すように、これははるかに厳しい境界です。

n         p_n         approx 1    error%  approx 2    error%
1         2                            
10        29          31          6.90 
100       541         613         13.31
1000      7919        8840        11.63
10000     104729      114306      9.14    104921      0.18
100000    1299709     1395639     7.38    1301789     0.16
1000000   15485863    16441302    6.17    15502802    0.11
10000000  179424673   188980382   5.33    179595382   0.10

の第 2 近似、 の第 1 近似、および最初の 5 つの素数の配列ルックアップを使用するために、 n番目の素数近似関数を実装しました。n >= 70226 <= n < 7022

(最初の方法は、特に私が使用する範囲では、非常に厳密な境界ではありませんが、ふるいにこれが必要なため、気にしません。小さい数のふるいは計算コストが低くなります。)

于 2009-07-01T13:00:36.923 に答える
4

素数定理は、しきい値を下回る素数の数を与えるため、n 番目の素数の近似値を与えるために使用できます。

于 2009-06-25T08:12:16.307 に答える
0

ふるいでは効率的な実装はおそらく不可能です。最初の 10.000 個の素数を取得したい場合はどうなるか考えてみてください。おそらく、非常に多くの数をふるいにかけなければならないでしょう。

この質問へのあなた自身の実装と私の答えは、アプリを知らなくてもこれを実装する良い方法です。素数の値

于 2009-06-25T10:16:53.810 に答える
0

私の最高の素数（n）推定

1/2*(8-8.7*n-n^2+
1/2*(2*abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+
abs((log(log(3))-log(log(n))+2*n*log(log(n)/log(2))+
sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+
log(log(n)))*log(log(n)/log(2))))/log(log(n)/log(2))))*(-1+
abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+abs(-(1/2)+n+
sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+
log(log(n)))*log(log(n)/log(2)))/(2*log(log(n)/log(2))))))

これが私の最新のより実験的な式です。ところで。10 兆番目の素数は323,780,508,946,331、この式がそのスケールで非常にうまく機能することであり、n*ln(n)+n*(ln(ln(n))-0.9385).

1/2*(3-(8+ln(2.3))*n-n^2+1/2*(-1+
abs(-(1/2)+n+sqrt(ln(ln(n)/ln(2))*(-ln(ln(2))+ln(ln(n))+
(8*ln(3)*ln((n*ln(8*n))/ln(n)))/ln(2)))/(2*ln(ln((n*ln(8*n))/
ln(n))/ln(2))))+abs(ln(n)/ln(3)+ln(ln((n*ln(8*n))/ln(n))/ln(2))/
ln(2)))*(2*abs(ln((n*ln(8*n))/ln(n))/ln(3)+ln(ln((n*ln(8*n))/ln(n))/
ln(2))/ln(2))+abs(1/ln(ln(n)/ln(2))*(ln(ln(3))-ln(ln(n))+2*n*ln(ln(n)/
ln(2))+sqrt(((8*ln(3)*ln(n))/ln(2)-ln(ln(2))+ln(ln((n*ln(8*n))/ln(n))))*
ln(ln((n*ln(8*n))/ln(n))/ln(2)))))))
于 2012-02-28T18:49:47.877 に答える