Nth prime
Nth prime calculator
Which prime comes 100th, or millionth? Or run it backwards and count how many primes lie below a number.
The 100th prime is 541
- 99th prime
- 523
- 101st prime
- 547
How close do the formulas get?
- Prime number theorem: n ln n ≈ 461 (under by 80, 14.8%)
- Guaranteed bounds: n(ln n + ln ln n − 1) = 513 < pn < n(ln n + ln ln n) = 614
Counting primes in order
Number the primes from the start: the 1st is 2, the 2nd is 3, the 10th is 29 and the 100th is 541. No known formula jumps straight to the nth prime, so the calculator counts them with a segmented sieve of Eratosthenes up to a ceiling that is guaranteed to be past the answer.
That ceiling comes from proven bounds. For n ≥ 6:
n(ln n + ln ln n − 1) < pn < n(ln n + ln ln n)
The prime number theorem gives the simpler estimate pn ≈ n ln n, and the result shows how far off it is. For n = 1,000,000 it gives 13,815,511 against the true 15,485,863; Rosser proved in 1939 that n ln n always falls short.
The second mode runs the other way. The prime-counting function π(x) is how many primes are less than or equal to x. π(100) = 25, so 97, the largest prime below 100, is the 25th prime. Gauss noticed as a teenager that π(x) stays close to x / ln x; the prime number theorem, proved in 1896, confirms that the ratio of the two tends to 1.
Sources
- Rosser JB. The n-th prime is greater than n log n. Proceedings of the London Mathematical Society 45 (1939), 21–44; Dusart P. The kth prime is greater than k(ln k + ln ln k − 1) for k ≥ 2. Mathematics of Computation 68 (1999), 411–415.
- Prime number theorem (Hadamard and de la Vallée Poussin, 1896) and the bounds for pn.
- OEIS A006988: the (10n)th prime, used to test this page.
Questions
What is the millionth prime?
15,485,863. The ten-millionth is 179,424,673 and the 50-millionth, the largest this page finds, is 982,451,653.
How long does a large n take?
The 50-millionth prime means sieving about a billion numbers: two to three seconds on a laptop, longer on a phone. It runs in a background worker with a progress bar, and Stop or a new number cancels it.
Is 1 counted as the first prime?
No. 1 is not prime, so the list starts 2, 3, 5, 7. Some old tables did include 1, which shifts every position by one; modern tables, including OEIS, do not.