math - 有没有办法找到第n个素数的近似值？

Question

是否有一个函数可以返回第 n 个素数的近似值？我认为这类似于近似逆素数计数函数。例如，如果我给这个函数 25 它会返回一个大约 100 的数字，或者如果我给这个函数 1000 它会返回一个大约 8000 的数字。我不在乎返回的数字是否是质数，但我确实想要它很快(因此不会生成前 n 个素数来返回第 n 个。)

我想要这个，以便我可以使用筛子( Eratosthenes 或 Atkin )生成前 n 个素数。因此，理想情况下，第 n 个素数的近似值永远不会低估实际第 n 个素数的值。

(更新:参见 my answer 寻找第 n 个素数上限的好方法。)

Answer 1

更严格的界限:

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 个素数，你可以这样做:

Cipolla 1902(参见 Dusart 1999 第 12 页或 this paper 。我发现三个项 (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 个则在几秒钟内完成(在现代快速机器上)。近似值在所有大小下都非常快，并且适用于更大的数字，但每个人对“大”的含义都有不同的理解。