是否有一个函数可以返回第n个素数的近似值？我认为这将类似于近似反向素数计数功能。例如，如果我给这个函数25它将返回一个大约100的数字，或者如果我给这个函数1000它将返回一个大约8000的数字。我不在乎返回的数字是否是素数，但我确实想要它要快（所以不产生前n个素数以返回第n个。）
我想这样我可以使用筛子（Eratosthenes或Atkin）生成前n个素数。因此，理想情况下，n th的近似值永远不会低估实际第n个素数的值。
（更新：请参阅my answer找到第n个素数的上限的好方法。）
更严格的界限：
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个素数，你可以这样做：
最后，如果您有一个非常快速的素数计数方法，例如一个LMO实现（现在有三个开源实现），您可以编写一个快速精确的nth_prime方法。计算10 ^ 10th素数可以在几毫秒内完成，10 ^ 13th在几秒钟内完成（在现代快速机器上）。所有尺寸的近似值都非常快，适用于更大的数字，但每个人对“大”的含义都有不同的看法。
感谢所有这些答案。我怀疑那里有一些相当简单的东西，但我当时找不到它。我也做了一些研究。
因为我希望sieve生成前n个素数，我希望近似值大于或等于第n个素数。 （因此，我想要第n个素数的上限。）
Wikipedia给出了n >= 6的以下上限
p_n <= n log n + n log log n (1)
其中p_n是第n个素数，而log是自然对数。这是一个良好的开端，但它可能会高估一个不可忽视的数额。在This article的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
我实现了我的第n个近似逼近函数，使用n >= 7022的第二个近似值，6 <= n < 7022的第一个近似值，以及前5个素数的数组查找。
（虽然第一种方法不是非常严格的限制，特别是对于我使用它的范围，我并不担心，因为我想要这个用于筛子，而且数量较少的筛子在计算上很便宜。）
Prime number theorem给出了一些低于阈值的素数，因此它可以用来给出第n个素数的近似值。
作为粗略估计，您可以使用n * ln（n）作为第n个素数的近似值。有一个更复杂但更准确的方法，您可以在维基百科here上找到详细信息。
我最好的Prime（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)))))))
使用筛子可能无法实现高效实施。想想如果你想拥有前10,000个素数会发生什么。你可能需要对更大量的数字进行筛选。
你自己在qazxsw poi和qazxsw poi中的实现是在不知道appr的情况下实现它的好方法。素数的价值
为了补充Dana J的上限，这个公式应该给你一个很好的下界。
this question