2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Yes, the $n$th prime is in that range, and nothing the sieve does for you on that range can pick it out without more information. The computation of the $n$th prime number is essentially inverse to computing the *prime counting function*, which has been discussed here from time to time. That is, if $p_n$ is the $n$th prime number, the count of primes less than or equal to $p_n$ is $n$, symbolically $\pi(p_n) = n$. $\endgroup$ – hardmath Aug 27 '15 at 12:33
  • $\begingroup$ Given all the work you've already done, I would suggest computing $x = \lfloor n \ln n \rfloor$ and checking $\pi(x)$. You can then count forward or backward through the primes you sieved out to find the $n$th prime in the range above or below $x$. $\endgroup$ – hardmath Aug 27 '15 at 12:41
  • $\begingroup$ What's that π(x)? $\endgroup$ – gvidoje Aug 27 '15 at 12:42
  • 1
    $\begingroup$ $\pi(x)$ is the prime counting function, the number of primes less than or equal to $x$, as explained in the first comment. $\endgroup$ – hardmath Aug 27 '15 at 12:43
  • $\begingroup$ Thanks a bunch guys, gotta eat dinner then I'm going to solve the problem. $\endgroup$ – gvidoje Aug 27 '15 at 12:49
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Rather than putting extra work into "a better... lower bound", I would put extra work into approximating $p_n$ better than $n \ln n$, since we can go forward or backward from there (and your $L$ is apt to be a long way off). There were some suggestions in comments on this older Question. $\endgroup$ – hardmath Aug 27 '15 at 13:34
  • 1
    $\begingroup$ @hardmath: Yes I know, actually this is only a basic description assuming only nextprime. More helpful hints can be found here in the answers of math.stackexchange.com/users/117584/danaj or in the implementations at Dana's page search.cpan.org/~danaj $\endgroup$ – gammatester Aug 27 '15 at 13:41
2
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.