n番目の素数のおおよその値を見つける方法はありますか？
https://stackoverflow.com/questions/1042717
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian解決
より狭い範囲：
static const unsigned short primes_small[] = {0,2,3,5,7,11};
static unsigned long nth_prime_upper(unsigned long n) {
double fn = (double) n;
double flogn, flog2n, upper;
if (n < 6) return primes_small[n];
flogn = log(n);
flog2n = log(flogn);
if (n >= 688383) /* Dusart 2010 page 2 */
upper = fn * (flogn + flog2n - 1.0 + ((flog2n-2.00)/flogn));
else if (n >= 178974) /* Dusart 2010 page 7 */
upper = fn * (flogn + flog2n - 1.0 + ((flog2n-1.95)/flogn));
else if (n >= 39017) /* Dusart 1999 page 14 */
upper = fn * (flogn + flog2n - 0.9484);
else /* Modified from Robin 1983 for 6-39016 _only_ */
upper = fn * ( flogn + 0.6000 * flog2n );
if (upper >= (double) ULONG_MAX) {
/* Adjust this as needed for your type and exception method */
if (n <= 425656284035217743UL) return 18446744073709551557UL;
fprintf(stderr, "nth_prime_upper overflow\n"; exit(-1);
}
return (unsigned long) ceil(upper);
}
これらは実際のnth_primeよりも小さくてはならず、64ビット入力で動作し、前述のRobinの式（またはWimblikの複雑な範囲制限の式）よりも1桁以上近いはずです。私の使用のために、私はわずかに大きい小さな素数テーブルを持っているので、最後の推定値をもう少しきつく締めることができます。技術的には、ceil（）の代わりにfloor（）を使用できますが、精度が心配です。
編集：これを少し改善するための別のオプションは、適切な素数の境界（たとえば、Axler 2014）を実装し、それらに対してバイナリ検索を実行することです。このメソッドの私のコードは、上記よりも約10倍長くなります（1ミリ秒未満で実行されます）が、エラーの割合を1桁減らすことができます。
n番目の素数の推定値が必要な場合は、次の操作を実行できます。
- Cipolla 1902（ Dusartを参照1999 12ページまたはこのペーパー。 3つの項（m = 2）に加えて3次の補正係数が有用ですが、より多くの項があると振動しすぎます。Wikipediaリンクに示されている式はこの式です（m = 2）。または以下の逆リーマンRはより良い結果をもたらします。
- Dusart 2010の上限と下限を計算し、結果を平均します。それほど悪くはありませんが、境界が同様にきつくないので、加重平均を使用するとうまくいくと思います。
- li ^ {-1}（n）li（n）は素数の適切な近似であるため、逆は適切なnth_prime近似です。これ、およびその他すべては、関数のバイナリ検索としてかなり迅速に実行できます。
- li ^ {-1}（n）+ li ^ {-1}（sqrt（n））/ 4 Closer、これはR（n）に近づいているためです
- R ^ {-1}逆リーマンR関数は、合理的であることがわかっている最も近い平均近似です。
最後に、LMO実装（現在3つのオープンソース実装がある）のような非常に高速な素数計算メソッドがある場合、高速で正確なnth_primeメソッドを記述できます。 10 ^ 10番目の素数の計算は数ミリ秒で、10 ^ 13番目の計算は数秒で行えます（最新の高速マシン上）。近似は、すべてのサイズで非常に高速で、はるかに大きな数で機能しますが、<！> quot; large <！> quot;
他のヒント
これらすべての回答に感謝します。私はそのようなかなり単純なものがあると疑っていましたが、その時はそれを見つけることができませんでした。私ももう少し研究をしました。
sieve が最初の n 素数、近似が n 番目の素数以上になるようにします。 （したがって、 n 番目の素数の上限が必要です。）
ウィキペディアは、n >= 6
p_n <= n log n + n log log n (1)
p_nは n 番目の素数で、logは自然対数です。これは良いスタートですが、少なからず過大評価する可能性があります。 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
6 <= n < 7022の2番目の近似、<=>の最初の近似、および最初の5つの素数の配列ルックアップを使用するために、 n 番目の素近似関数を実装しました。
（最初の方法は、特に私が使用する範囲についてはあまり厳密ではありませんが、ふるいにこれが欲しいので心配していません。小さな数字のふるいは計算的に安価です。）
素数定理は、しきい値以下の素数を与えるため、 n番目の素数のおおよその値を与えるために使用されます。
概算として、n * ln（n）をn番目の素数の近似として使用できます。はるかに複雑ですが、より正確な方法があります。詳細については、Wikipedia こちら。
マイベストプライム（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)))))))
Dana Jの上限を補完するために、この式は適切な下限を提供します。
P(n) = (((2 Log(3, n + 2))/(Log(2.5, 2) + Log(3, 3)) + (2 Log(3, n - 2))/(Log(3, 2) + Log(3, 3)))/2) n;
