是否有一个函数可以返回第 n 个素数的近似值?我认为这类似于近似逆素数计数函数。例如,如果我给这个函数 25 它会返回一个大约 100 的数字,或者如果我给这个函数 1000 它会返回一个大约 8000 的数字。我不在乎返回的数字是否是质数,但我确实想要它很快(因此不会生成前 n 个素数来返回第 n 个。)
我想要这个,以便我可以使用筛子( Eratosthenes 或 Atkin )生成前 n 个素数。因此,理想情况下,第 n 个素数的近似值永远不会低估实际第 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^10 个素数可以在几毫秒内完成,而第 10^13 个则在几秒钟内完成(在现代快速机器上)。近似值在所有大小下都非常快,并且适用于更大的数字,但每个人对“大”的含义都有不同的理解。
关于math - 有没有办法找到第n个素数的近似值?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1042717/