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

Question

是否有一个函数可以返回第n个素数的近似值？我认为这将类似于近似反向素数计数功能.例如,如果我给这个函数25它将返回一个大约100的数字,或者如果我给这个函数1000它将返回一个大约8000的数字.我不在乎返回的数字是否是素数,但我确实想要它要快(所以不产生前n个素数以返回第n个.)

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

(更新:请参阅我的答案,找到找到第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页或本文.我发现三个术语(m = 2)加上三阶校正因子是有用的,但更多的术语它振荡太多.维基百科链接中显示的公式是这个公式(m = 2).使用下面的两项逆li或逆Riemann R将得到更好的结果.
• 计算Dusart 2010的上限和下限并对结果取平均值.虽然我怀疑使用加权平均值会更好,因为边界不是同样紧张,但也不算太糟糕.
• li ^ { - 1}(n)由于li(n)是素数的理想近似值,因此逆是nth_prime近似值.这个,以及所有其余的,可以作为对函数的二进制搜索相当快地完成.
• li ^ { - 1}(n)+ li ^ { - 1}(sqrt(n))/ 4更接近,因为这越来越接近R(n)
• R ^ { - 1}逆Riemann R函数是我知道的最接近的平均近似值是合理的.

最后,如果您有一个非常快速的素数计数方法,例如一个LMO实现(现在有三个开源实现),您可以编写一个快速精确的nth_prime方法.计算10 ^ 10th素数可以在几毫秒内完成,10 ^ 13th在几秒钟内完成(在现代快速机器上).所有尺寸的近似值都非常快,适用于更大的数字,但每个人对"大"的含义都有不同的看法.

Answer 2

感谢所有这些答案.我怀疑那里有一些相当简单的东西,但我当时找不到它.我也做了一些研究.

因为我想要筛子生成前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个素数的数组查找.

(虽然第一种方法不是非常严格的限制,特别是对于我使用它的范围,我并不担心,因为我想要这个用于筛子,而且数量较少的筛子在计算上很便宜.)