How do we identify the $n$th prime?

Question

The 1st prime is 2. The 2nd prime is 3. The 3rd prime is 5. So if $\pi(x)=1$, the prime is 2. If $\pi(x)=2$, the primes are 2 and 3, but how do we identify them? If $\pi(x)=3$, I know that there are 3 primes, but how can I find what each one is? Of these three, the first is 2, the second is 3, and the third is 5. Now, if $\pi(x)=25$ and I want to identify the 24th prime, how would I do this?

Answer 1

You could test numbers in turn, checking if they are prime by trial division, until you produced the desired prime. This takes time $O(n^{3/2})$ and space $O(\log n)$.

To reduce time you might instead make a list of the numbers up to roughly $1.01n\log n$ and use the Sieve of Eratosthenes to identify the primes up to that point, then count off primes until the desired one is reached. This takes time $O(n\log n\log\log n)$ but space increases to $O(n\log n)$.

You could segment the sieve, working in chunks of size $\sqrt{n\log n}$. This keeps the time at $O(n\log n\log\log n)$ but decreases the space to $O(\sqrt{n\log n})$. (You could make the space smaller only at the cost of increasing the time.)

But there are better ways! If you had a good guess for the n-th prime, you could count the number of primes up to that number and see how far off you were, using that as a basis for a more accurate guess. This would only help if you had a fast way to count primes up to a given bound $x$, but we do, thanks to Deléglise & Rivat who give a method which works in time $O(x^{2/3}/\log^2x)$ and space $O(x^{1/3}\log^3x\log\log x)$. Using a binary search to find the n-th prime takes time $O(n^{2/3}/\log^{1/3}x)$ and space $O(n^{1/3}\log^{10/3}n\log\log n)$, and practically speaking a binary search isn't needed -- one or at most two applications plus sieving should suffice if a good approximation (like the inverse logarithmic integral) is used.

A number of authors have improved on the speed of computing the prime-counting function by moving from the combinatorial methods of Deléglise & Rivat to analytic methods (Lagarias & Odlyzko; Galway; Franke, Kleinjung, Jost, & Buethe; Platt). I believe these all operate in time $O(x^{1/2+\varepsilon})$ giving time $O(n^{1/2+\varepsilon})$. I don't know what the best space requirement is but I believe $O(x^{1/4+\varepsilon})$ can be achieved.

A more practical method for smaller $n$ can be found here: Booker's n-th Prime Page Algorithm. This method uses a large amount of precomputation to give answers quickly over a (relatively) small range.

So rather a lot is known about this problem; hopefully this overview is helpful.

Answer 2

I don't think there is a way to do it. Anyway if it can help,
you can use the asymptotic formula $p_n\sim n\cdot ln(n)$. To get more information about $\pi(x)$ look here http://en.wikipedia.org/wiki/Prime_number_theorem