7个回答
13
更严格的界限：
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);
}
这些估算不应该低于实际的第n个质数，适用于任何64位输入，比Robin之前给出的公式（或Wimblik的复杂范围限制公式）更接近一个数量级或更多。对于我的用途，我有一个稍大一些的小质数表，因此可以更加紧密地缩小最后的估计。从公式上讲，我们可以使用floor()而不是ceil()，但我担心精度问题。
编辑：另一种改进方法是实现良好的素数计数界限（例如Axler 2014），并在它们上进行二分查找。 我的代码使用这种方法要比上面的方式慢大约10倍（仍然在1毫秒内运行），但可以将误差百分比降低一个数量级。
如果您想要第n个质数的估计值，可以进行以下操作：
- Cipolla 1902（参见Dusart 1999第12页或此论文）。 我发现三项（m = 2）加上三阶修正因子很有用，但是使用更多项会产生太多波动。 在维基百科链接中显示的公式即为此公式（其中m = 2）。 使用下面的两项反li或反黎曼R将获得更好的结果。
- 计算Dusart 2010的上下界并平均结果。 不错，尽管我认为使用加权平均值效果更好，因为界限不是完全紧密的。
- li^{-1}(n) 由于li(n)是素数计数的一个不错的近似值，因此其倒数是一个不错的第n个质数的近似值。 所有这些方法都可以通过函数的二分查找来快速完成。
- li^{-1}(n) + li^{-1}(sqrt(n))/4 更接近，因为它越来越接近R(n)
- R^{-1} 反黎曼R函数是我知道的最接近平均值的适当近似。
最后，如果您拥有非常快的素数计数方法，例如LMO实现之一（现在有三个开源实现），则可以编写快速精确的第n个质数方法。 计算第10^10个质数只需几毫秒，而计算第10^13个质数只需几秒钟（在现代快速计算机上）。 所有大小的近似值都非常快速，并且适用于更大的数字，但每个人对“大”有不同的想法。
- DanaJ
6
这是最好的答案，但我认为其中有一个小小的错误。语句
flogn = log(flogn); 可能应该是 flog2n = log(flogn);。 - President James K. Polk@GregS，谢谢！已修复。我还添加了一段关于使用反素数计数界限的内容。 - DanaJ
@DarshanPatil 这与Christian Axler的估计相差甚远（https://www.emis.de/journals/JIS/VOL22/Axler/axler17.pdf），而这是目前该主题上最好的工作。 - vitaly-t
@vitaly-t 是的，我同意。感谢您让我知道！✌️ - user16657590
我尝试了这里的解决方案，前1000个质数后估计值误差率小于1%，看起来还不错。但是对于前1000个质数，这里的估计值很糟糕，误差率远高于1%。 - vitaly-t
11
感谢所有的回答，我本来就觉得应该有一个相当简单的方法，但那时候我找不到。我也做了更多的研究。
由于我想用它来生成前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
我实现了第 n 个质数的近似函数，当 n >= 7022 时使用第二种近似方法，当 6 <= n < 7022 时使用第一种近似方法，并对前5个质数进行数组查找。
尽管第一种方法在我使用它的范围内并不是一个非常紧密的界限，但我并不担心，因为我想用这个筛子来筛选较小的数字，而筛选较小的数字是计算便宜的。
- David Johnstone
6
7很遗憾，这个公式似乎出现了问题。
p_8597 = 88789，但是该公式给出的结果是88759.3，比实际值低。看起来当 n >= 8602 时这个公式可能没问题。 - Charphacy1从检查素数到2e9，我得到了：
p_8621 = 89009, p ∈ [88746.2, 89014.4], delta ∈ [-0.9718, -0.9407]。通过选择8621，您可以使用常量-0.9407获得略微更好的近似值。下一个改进在p_15957处。是的，这篇论文一定是错的。 - starblue1根据Dussart的论文，n > 39017实际上成立： "对于k≥2，第k个质数大于k(lnk+lnlnk−1)。"，Math. Comp.，68（225），411 - 415。 - G. Bach
1@DavidJohnstone：文章链接似乎已经失效了。请问您能提供一个更新的链接吗？ - Gaurav
1@Gaurav，这是一篇目前有效的论文链接，题为《第N个质数的上界》：https://www.maa.org/sites/default/files/jaroma03200545640.pdf - I. J. Kennedy
1
为了补充 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;
- AnaloDim Ripe AnaloDimRipe
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))))))
这是我最近更为实验性的公式。
顺便说一下，第十万亿个质数是 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)))))))
- Quoss P Wimblik
1
这两个都不起作用。我输入了1000，却得到了一个负数。 - vitaly-t
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接