Programming Praxis

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 p_n. It is true for all positive integers n that π(p_n) = 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.

Pages: 1 2