The nth Prime and How Many Primes

This finds the $n$th prime and how many primes lie below a limit you choose, using the sieve of Eratosthenes.

List the numbers from 2 upwards and strike out the multiples of 2, then of 3, then of 5, and so on. Whatever survives is prime. It counts far faster than testing each number by division.

Example

The hundredth prime is 541. There are 168 primes up to 1000, 1229 up to 10000 and 9592 up to 100000: the further you go, the more thinly they are spread.

Roughly how many there are

The count of primes up to $x$ is about $\dfrac{x}{\ln x}$. This is the prime number theorem.

For $x = 1000$ that gives $1000 \div 6.91 \approx 145$, close to the true value of 168. The larger $x$ becomes, the smaller the relative error of this estimate.

Notes

The sieve needs room proportional to the limit, so $n$ goes up to 50000 and the counting limit up to 1000000.

1 is not prime. The primes start at 2.