Is there a way to find the approximate value of the nth prime?

Question

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

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

Answer 1

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

Answer 2

http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number

Answer 3

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

Answer 4

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

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

Answer 5

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

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

Wikipedia gives the following upper bound for n >= 6

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

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

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

This is a much 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 implemented my nth prime approximation function to use the second approximation for n >= 7022, the first approximation for 6 <= n < 7022, and an array lookup for the first 5 prime numbers.

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