How to use it
- Choose “The n-th prime” and enter n, or choose “How many primes up to x” and enter x.
- Read the prime or the count, with the primes just before and after.
How it works
The Sieve of Eratosthenes marks every odd multiple of 3, 5, 7 … as composite, starting at the square of each prime. For the n-th prime the sieve runs up to Rosser’s bound m(ln m + ln ln m) with m = n + 1, which is always beyond the (n + 1)-th prime, so the next prime is found as well; the calculator then counts primes until it reaches the n-th. For π(x) it sieves a little past x so it can also show the next prime.
Worked example
The 100th prime: the bound is 101 × (ln 101 + ln ln 101) ≈ 621, the sieve finds the primes up to it, and the 100th of them is 541. The 99th is 523 and the 101st is 547. In the other direction, π(541) = 100, and 541 is the 100th prime.
Tips
- By the prime number theorem, π(x) is roughly x / ln x: for x = 1,000,000 that gives about 72,382 against the true 78,498.
- To test one big number for primality, use the prime number checker, which goes far beyond 20 million.