有没有办法求出第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 复杂的范围限制公式）要大一个数量级或更接近。对于我的使用，我有一个稍大的小素数表，因此可以稍微收紧最后的估计。从技术上讲，从公式来看，我们可以使用 Floor() 而不是 ceil()，但我担心精度。
编辑：稍微改进这一点的另一个选择是实现良好的素数计数界限（例如Axler 2014）并对它们进行二分搜索。我的此方法的代码比上面的代码花费了大约 10 倍的时间（仍然运行在不到一毫秒），但可以将错误百分比降低一个数量级。
如果你想估计第 n 个素数，你可以这样做：
- 西波拉 1902（见 杜萨尔 1999 第 12 页或 这张纸. 。我发现三项 (m=2) 加上三阶校正因子很有用，但项越多，它的振荡就越大。维基百科链接中显示的公式就是这个公式（m=2）。使用下面的两项逆 li 或逆黎曼 R 会得到更好的结果。
- 计算 Dusart 2010 上限和下限并对结果求平均值。还不错，但我怀疑使用加权平均值会更好，因为界限并不同样严格。
- li^{-1}(n) 由于 li(n) 是素数计数的一个不错的近似值，因此其逆是一个不错的 nth_prime 近似值。这以及所有其他的事情，都可以通过对函数进行二分搜索来相当快地完成。
- li^{-1}(n) + li^{-1}(sqrt(n))/4 更接近，因为这越来越接近 R(n)
- R^{-1} 黎曼 R 函数的反函数是我所知道的最接近的平均近似值，这是合理的。
最后，如果您有一个非常快速的素数计数方法，例如 LMO 实现之一（现在有三个开源实现），您可以编写一个快速精确的 nth_prime 方法。计算第 10^10 个素数可以在几毫秒内完成，计算第 10^13 个素数只需几秒钟（在现代快速机器上）。近似值在所有大小上都非常快，并且适用于更大的数字，但每个人对“大”的含义都有不同的理解。
其他提示
感谢所有这些答案。我怀疑有这样一个相当简单的东西，但当时我找不到它。我也做了更多研究。
因为我想要它 筛 生成第一个 n 素数，我希望近似值大于或等于 nth素数。（因此，我想要的上限 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 个素数的数组查找。
（虽然第一种方法不是一个非常严格的界限，特别是对于我使用它的范围，但我并不担心，因为我想要这个筛子，并且较小数字的筛子在计算上是便宜的。）
素数定理给出了多个阈值以下的素数，所以它可能是用于为第n个素数的近似值。
作为粗略估计，可以使用N * LN（n）作为第n个素数的近似值。还有一个更复杂，但更准确的方法，其中的细节，你可以找到关于维基百科这里
我最好素（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)))))))
要补充达纳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;
