17

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

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

（更新：请参阅我的答案，了解找到第n个素数上限的好方法。）

4

7 回答 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);
}

这些不应该小于实际的 nth_prime，应该适用于任何 64 位输入，并且比之前给出的 Robin 的公式（或 Wimblik 的复杂范围限制公式）一个数量级或更接近。对于我的使用，我有一个稍大的小素数表，因此可以进一步加强最后的估计。从技术上讲，我们可以使用 floor() 而不是 ceil() 的公式，但我担心精度。

编辑：改进这一点的另一个选择是实现良好的素数边界（例如 Axler 2014）并对它们进行二进制搜索。我的这种方法的代码比上面的代码要长约 10 倍（仍然运行在一毫秒以下），但可以将错误百分比降低一个数量级。

如果你想估计第 n 个素数，你可以这样做：

  • Cipolla 1902（参见Dusart 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 个素数可以在几秒钟内完成（在现代快速机器上）。近似值在所有尺寸下都非常快，并且适用于更大的数字，但每个人对“大”的含义都有不同的想法。

于 2014-08-22T06:12:59.733 回答
10

感谢所有这些答案。我怀疑有这样相当简单的东西，但当时我找不到。我也做了更多的研究。

因为我希望筛子生成前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 个素数的数组查找。

（虽然第一种方法的界限不是很紧，尤其是对于我使用它的范围，但我并不担心，因为我想要这个作为筛子，而且数字较小的筛子在计算上很便宜。）

于 2009-07-01T13:00:36.923 回答
4

素数定理给出了低于阈值的素数，因此它可以用来给出第 n 个素数的近似值。

于 2009-06-25T08:12:16.307 回答
4

作为粗略估计，您可以使用 n*ln(n) 作为第 n 个素数的近似值。有一种更复杂但更准确的方法，您可以在 此处的 Wikipedia 上找到详细信息。

于 2009-06-25T09:16:17.443 回答
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;
于 2017-12-21T06:00:03.023 回答
0

使用筛子可能无法实现有效的实施。想想如果你想拥有前 10.000 个素数会发生什么。你可能不得不对大量的数字进行筛选。

你自己在这个问题中的实现和我的回答是在不知道 appr 的情况下实现这个的好方法。质数的值

于 2009-06-25T10:16:53.810 回答
0

我的最佳 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))))))

这是我最近的更多实验公式。顺便提一句。第 10 万亿个素数是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)))))))
于 2012-02-28T18:49:47.877 回答