How do I find(isolate) the n-th prime number?

Question

So I wanted to solve this SPOJ problem and I did some research about finding the n-th prime number. This formula came across and it stated that the n-th prime must be in this range:

$n \ln n + n(\ln\ln n - 1) < p_n < n \ln n + n \ln \ln n$ for $n\ge{}6$ (1)

Thus I used the segmented sieve of Eratosthenes in the following manner:

1. Read in the number n
2. Calculate the lower and upper bound by the given formula (1)
3. Construct an array of divisor primes for the segment, (primes till the square root of the upper bound)
4. Sieve through the range lower till upper (using the algorithm for the segmented sieve)

After that I was left with all the prime numbers in the calculated range, and as it appeared there were more primes than just the one I desired, so naturally the question arises, how do I know which one is the desired n-th prime and how can I isolate it from the rest?

Answer 1

Since your question relates to a programming task, here a method I have implemented to compute the $k$th prime (in Pascal for a slightly smaller range):

1. Get a better estimate for the lower bound $L \le p_k$ of $p_k$ e.g. from P. Dusart, 1999, The $k$th prime is greater than $k(\log k + \log \log k - 1)$ for $k\ge 2$, Math.Comp.68, available here. Compute the next prime $p \ge L.$

2. Compute $m=\pi(p)$ e.g. using the Meissel-Lehmer method.

3. If $m=k$ you are done with $p_k=p$, otherwise increment $m$ and repeat this step with $p=\mathrm{nextprime}(p+1).$

This is really a programming task. The Dusart approximation is trivial to implement, the nextprime function is not but it is handy and needed in many situations. The Meissel-Lehmer method is described e.g. by T. Oliveira e Silva, Computing pi(x): the combinatorial method. The text including a simple implementations in C (see Table II) is available as http://www.ieeta.pt/~tos/bib/5.4.pdf

Answer 2

This is a very similar question to Most efficient algorithm for nth prime, deterministic and probabilistic?

There are quite a few ways, depending on how much you want to optimize, what your expected range is, and how much code you want to write. If you don't have very large inputs, you can compute (easily) an upper bound, then use a segmented sieve counting as you go. For the SPOJ problem you give, it looks tight on time to me (sieve and count to 2.3e10 in under 3 seconds). Even primesieve would be very pressed for time. Some clever tables could reduce the work a lot with very little source, making it quite possible (since your range really isn't all that large).

gammatester gives a good answer, but as the answers on the other question note, and hardmath points out in his comment, we can improve. Get a good estimate (e.g. $R^{-1}$), perform a fast prime count algorithm, then sieve segments and count forward or backward as needed. In my code I was lazy and wrote a fast sieve forward count but just a prev_prime loop going backwards. So I bias my estimate a little under. I use ${\rm Li}^{-1}(n)+{\rm Li}^{-1}(\sqrt{n})/4$ which gets very close but is rarely over, and not by much when it is. If you were symmetrical then either $/2$ in the latter formula or go with inverse Riemann R.

At 5000 bytes of source, this also is a bit constrained as we're not going to write LMO. For this size of n, the simpler methods of Legendre, Meissel, or Lehmer with a simple phi function ought to work just fine. Riesel (1994) should have everything needed, and TOeS's paper referenced by gammatester has a simple Legendre implementation. Note Table II is a rudimentary Legendre (1830) algorithm, which is slower than Meissel or Lehmer and much slower than the extended LMO the paper is really about; implementing the latter is not easy and his paper is a long tough slog to working code. It may be good enough for this problem however, and there are lots of not-complicated optimizations possible for phi(x,a).

Addendum. For the very practical, some methods and programs:

• Go to Wolfram Alpha, type Prime[n] where n is your number.
• https://primes.utm.edu/nthprime/ Uses very dense tables followed by sieving with primesieve.
• http://sti15.com/nt/nthprime.cgi an example page using my code on a slow web server. Limited to 10^12 to be kind to other clients. It's just a 1990's web wrapper around perl -E 'use ntheory ":all"; say nth_prime(...)'
• https://github.com/kimwalisch/primecount Kim Walisch's excellent primecount project. Fastest open source implementation on multiple cores, and works on >64-bit inputs as well.
• https://github.com/danaj/Math-Prime-Util my C code inside a Perl module, though most of it can be compiled as standalone C. A little faster than primecount on a single thread.