The Nth Prime

August 2, 2011

We conclude the current series of exercises on the prime-counting function with this exercise on the inverse of the prime-counting function that returns the nth prime, denoted pn. It is true for all positive integers n that π(pn) = n.

Given Lehmer’s computation of the prime-counting function and Riemann’s approximation of the same function it is relatively easy to compute the nth prime: Use Riemann’s approximation to estimate the value. Apply Lehmer’s formula to the estimate and compute the exact value of π at the approximation. Count up or down as needed using either a sieve or a primality tester.

Your task is to write a function that computes the n prime, and to use it to compute the million’th prime. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

2 Responses to “The Nth Prime”

  1. [...] primes, not knowing the largest prime in the set. One method is to calculate the nth prime, using a prime-counting formula, then use the Sieve of Eratosthenes to generate the list. Or instead of calculating the nth prime [...]

  2. danaj said

    I just came across this, and I think it’s a great idea and can be done pretty easily with just simple functions (a good primality tester being one of them, which as we’ve seen through many of your exercises is a really handy tool tool to have). I will point out that the GNU MPFR library (available in C, Perl, and Python to name a few) has a fast high-precision Riemann Zeta function, leaving only the relatively straightforward Riemann R calculation to do.

    Rather than the search on Riemann R, an easier but somewhat slower way would be to use Cipolla’s nth prime approximation (Dusart 1999 page 12, among other sources) using, for instance, 3 terms (m=2). Then do Lehmer’s method on that and count up/down. Simple and straightforward, but we don’t get nearly as close as as using Riemann’s R function. I suppose it depends on how simple you want the code, how long Riemann R takes to compute, and how fast we can count.

    My original solution, before doing the Lehmer prime counting function, was just optimizing the straightforward approach — fast segment sieve and fast bit counting. Once I added Lehmer’s method, given I had a fast segmented prime count, the method I used: compute a lower limit (Dusart 2010, page 2), do Lehmer’s method to get that count, then do the sieve from that point. The Dusart lower limit is cheap and only has to be computed once. Of course it doesn’t get as close as a search on Riemann’s R. The other advantage is that segment counting is pretty fast vs. prev_prime / next_prime.

    Looking at 10^12 as an example:

    – Using Riemann R, we come up with 29996225393466. Lehmer’s count gives us 1000000035884, so we call prev_prime 35885 times and get 29996224275833. All but 0.5s is spent doing the prime count (I just used a binary search). Total time in my code 11.8s.

    – Using Cipolla’s approximation, we immediately get 29996300456744. Lehmer’s count gives us 1000002454213, then we count down to 29996224275833. Total time: 43.6s.

    – Using the lower+sieve method, we immediately get 29994075087860. Lehmer’s count gives us 999930740354. Since we used the lower limit, we know this will always be <= the target. We sieve from there and get 29996224275833. Total time: 19.2s.

    – Using just the sieve, we churn away until we get 29996224275833. Primesieve on 12 cores takes over 33 minutes, which goes to show just how much faster Lehmer's method is (especially as threaded primesieve is super fast as far as sieves go).

    It looks like, with my implementation, things are a wash in performance between the R-search+prev_prime/next_prime and lower+sieve methods until about 10^11, where your Riemann R method starts coming out ahead. For 10^13th it's over 3x faster. Definitely something I'll want to use at some point.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 574 other followers

%d bloggers like this: