有没有办法找到第n个素数的近似值? [英] Is there a way to find the approximate value of the nth prime?

问题描述

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

Is there a function which will return the approximate value of the n th prime? I think this would be something like an approximate inverse prime counting function. For example, if I gave this function 25 it would return a number around 100, or if I gave this function 1000 it would return a number around 8000. I don't care if the number returned is prime or not, but I do want it to be fast (so no generating the first n prime numbers to return the n th.)

我想这样做，以便可以使用筛子生成第一个 n 个质数( Atkin ).因此，理想地，对 n 的逼近永远不会低估实际 n 素数的值.

I would like this so that I can generate the first n prime numbers using a sieve (Eratosthenes or Atkin). Therefore, the approximation for n th the would ideally never underestimate the value of the actual n th prime.

(更新:请参见

(Update: see my answer for a good method of finding the upper bound of the n th prime number.)

推荐答案

更严格的限制:

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()，但我担心精度.

These should not ever be less than the actual nth_prime, should work for any 64-bit input, and be an order of magnitude or more closer than the formula from Robin given earlier (or Wimblik's complicated range-limited formula). For my use I have a slightly larger small primes table so can tighten up the last estimate a bit more. Technically from the formulas we could use floor() instead of ceil() but I worry about precision.

另一个改进方法是实现良好的质数范围(例如Axler 2014)并对其进行二进制搜索.我为此方法编写的代码比上述方法花费大约10倍的时间(仍然可以在毫秒内运行)，但是可以将错误百分比降低一个数量级.

Another option for improving this a bit is implementing good prime count bounds (e.g. Axler 2014) and doing a binary search on them. My code for this method takes ~10x longer than the above (still running in under a millisecond), but can reduce the error percentage by an order of magnitude.

如果要估算第n个素数，可以执行以下操作:

If you want an estimate for the nth prime, you can do:

• Cipolla 1902(请参阅 Dusart 1999 第12页或本文.三个项(m = 2)加上一个三阶校正因子很有用，但随着更多的项它会振荡太多.Wikipedia链接中显示的公式就是该公式(m = 2).或下面的逆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逆函数是我所知道的最接近的平均近似值.

• Cipolla 1902 (see Dusart 1999 page 12 or this paper. I find three terms (m=2) plus a third order correction factor to be useful, but with more terms it oscillates too much. The formula shown in the Wikipedia link is this formula (with m=2). Using the two-term inverse li or inverse Riemann R below will give better results.
• Calculate the Dusart 2010 upper and lower bounds and average the results. Not too bad, though I suspect using a weighted average will work better as the bounds aren't equally tight.
• li^{-1}(n) Since li(n) is a decent approximation to the prime count, the inverse is a decent nth_prime approximation. This, and all the rest, can be done fairly quickly as a binary search on the function.
• li^{-1}(n) + li^{-1}(sqrt(n))/4 Closer, since this is getting closer to R(n)
• R^{-1} The inverse Riemann R function is the closest average approximation I know that's reasonable.

最后，如果您有一个非常快的素数计数方法(例如LMO实现之一)(现在有三个开源实现)，则可以编写一个快速精确的nth_prime方法.可以在几毫秒内完成10/10质数的计算，而在几秒钟内(在现代快速计算机上)可以完成10 ^ 13质数的计算.近似值在所有大小下都非常快，并且适用于更大的数字，但是每个人对大"的含义都有不同的认识.

Lastly, if you have a very fast prime count method such as one of the LMO implementations (there are three open source implementations now), you can write a fast precise nth_prime method. Computing the 10^10th prime can be done in a few milliseconds, and the 10^13th in a couple seconds (on a modern fast machine). The approximations are extremely fast at all sizes and work for far larger numbers, but everyone has a different idea of what "large" means.

这篇关于有没有办法找到第n个素数的近似值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！