[ACCEPTED]-Is there a way to find the approximate value of the nth prime?-sieve

Accepted answer
Score: 14

Tighter bounds:

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

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

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

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

  • 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.

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

Score: 10

Thanks for all of those answers. I suspected 21 there was something fairly simple like that, but 20 I couldn't find it at the time. I've done 19 a bit more research too.

As I want it for 18 a sieve to generate the first n prime numbers, I 17 want the approximation to be greater than 16 or equal to the nth prime. (Therefore, I 15 want the upper bound of the nth prime number.)

Wikipedia gives 14 the following upper bound for n >= 6

p_n <= n log n + n log log n   (1)

where p_n is 13 the nth prime, and log is the natural logarithm. This 12 is a good start, but it can overestimate 11 by a not inconsiderable amount. This article in The College Mathematics Journal gives 10 a tighter upper bound for n >= 7022

p_n <= n log n + n (log log n - 0.9385)   (2)

This is a much 9 tighter bound as the following table shows

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

I 8 implemented my nth prime approximation function 7 to use the second approximation for n >= 7022, the 6 first approximation for 6 <= n < 7022, and an array lookup 5 for the first 5 prime numbers.

(Although 4 the first method isn't a very tight bound, especially 3 for the range where I use it, I am not concerned 2 as I want this for a sieve, and a sieve 1 of smaller numbers is computationally cheap.)

Score: 4

Prime number theorem gives a number of primes below a threshold 2 value, so it could be used to give an approximate 1 value for the nth prime.

Score: 4

As a rough estimate, you can use n*ln(n) as 4 an approximation for the nth prime number. There 3 is a much more complex, but more accurate 2 method, details of which you can find on 1 Wikipedia here.

Score: 1

To complement Dana J's Upper bound this 1 formula should give you a good lower bound.

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;
Score: 0

An efficient implementation is probably 7 not possible with a sieve. Think what would 6 happen if you want to have the first 10.000 5 prime numbers. You probably would have to 4 make a sieve over a huge bigger amount of 3 numbers.

Your own implentation in this question and my answer are 2 good ways to implement this without knowing 1 the appr. value of a prime

Score: 0

My Best Prime(n) Estimate

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))))))

Here's my most 4 recent more experimental formula. btw. The 3 ten trillionth prime is 323,780,508,946,331 this formula works 2 quite well at that scale not sure if it 1 continues to get closer than 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)))))))

More Related questions