An Nth Prime Calculator Has to Count Every Prime Before Yours
About the Author
Marko Šinko
Co-Founder & Lead Developer, AI Math Calculator
An nth prime calculator returns p₁₀₀₀ = 7,919 in about the time it takes to blink, and the explanation for how is slightly deflating: it found the other 999 primes first. There is no shortcut. Nothing takes 1,000 in one end and drops 7,919 out the other.
That one fact shapes the whole tool above — how far it has to sieve before it can answer, why it works harder the higher you climb, and why the estimate printed next to the answer is arguably more interesting than the answer. What follows is the bound that tells a program where to stop looking, two approximations for pₙ that differ twelvefold in accuracy, the counting function π(x) that runs the same question backwards, and the off-by-one that quietly wrecks half the answers people give.
There Is No Formula That Skips Straight to the nth Prime
Formulas do exist on paper. Willans published one in 1964 that expresses pₙ in closed form using nested floor functions and a cosine; Mills proved there is a constant θ ≈ 1.3063 such that ⌊θ^(3ⁿ)⌋ is prime for every n. Neither is usable. Willans’ version needs factorials of numbers around the size of pₙ itself, and θ can only be pinned down to enough decimal places by first knowing the primes it is supposed to produce. That is a circle, not a shortcut.
What actually runs is the sieve of Eratosthenes, unchanged in principle since roughly 240 BC. Write down every integer up to some limit, cross out multiples of 2, then multiples of 3, then 5, and count what survives. Reach a count of 1,000 and the number you are standing on is 7,919. The same crossing-out logic sits under a prime factorization calculator, except there you keep the divisors instead of discarding them.
Scaling is better than people expect. Finding p₁₀₀₀₀₀₀ = 15,485,863 means sieving 16.4 million numbers, but you only ever cross out using primes up to √16,400,000 ≈ 4,050 — about 560 of them. That is why the millionth prime comes back in well under a tenth of a second while a naive “test each number for primality” loop would still be grinding.
How an Nth Prime Calculator Decides Where to Stop Sieving
A sieve needs a finite array, so before it starts it needs an upper bound on pₙ. Rosser supplied one: for every n ≥ 6, pₙ < n(ln n + ln ln n). Sieve to that limit and the nth prime is guaranteed to be inside. Guess lower and you get a wrong answer or a second pass.
| n | Rosser bound | Actual pₙ | Wasted sieving |
|---|---|---|---|
| 1,000 | 8,841 | 7,919 | 11.6% |
| 10,000 | 114,307 | 104,729 | 9.1% |
| 100,000 | 1,395,640 | 1,299,709 | 7.4% |
| 1,000,000 | 16,441,303 | 15,485,863 | 6.2% |
The overshoot shrinks as n grows, which is convenient — the cases where wasted work would hurt are exactly the cases where the bound is tightest. Twelve per cent of extra crossing-out at n = 1,000 costs nothing at all; six per cent at a million costs a few milliseconds.
Two Estimates for pₙ, One of Them Twelve Times Better
The approximation everyone learns first is pₙ ≈ n ln n. It is asymptotically correct and practically disappointing. At n = 1,000 it says 6,908 against a true 7,919 — low by 12.8%. The frustrating part is that it barely improves with scale: at a million it is still low by 10.8%.
Add one more term and the character of the estimate changes completely. Using pₙ ≈ n(ln n + ln ln n − 1) the miss drops to 0.99% at n = 1,000 and to 0.29% at a million.
| n | Actual pₙ | n · ln n | Error | n(ln n + ln ln n − 1) | Error |
|---|---|---|---|---|---|
| 100 | 541 | 461 | −14.9% | 513 | −5.1% |
| 1,000 | 7,919 | 6,908 | −12.8% | 7,840 | −1.0% |
| 10,000 | 104,729 | 92,103 | −12.1% | 104,307 | −0.40% |
| 100,000 | 1,299,709 | 1,151,293 | −11.4% | 1,295,640 | −0.31% |
| 1,000,000 | 15,485,863 | 13,815,511 | −10.8% | 15,441,302 | −0.29% |
Notice every error is negative. That is not luck. Rosser also proved pₙ > n ln n for all n, so the textbook estimate is a guaranteed floor and never a ceiling. If you need a working number without running a sieve, take n(ln n + ln ln n − 1) and treat it as a lower bound you may need to walk up from.
π(x) Is the Same Question Read Backwards
The prime-counting function π(x) gives how many primes are less than or equal to x. It is the exact inverse of prime indexing: π(pₙ) = n. Ask “which prime is number 1,000” and you get 7,919; ask “how many primes are there up to 7,919” and you get 1,000. Same pair of numbers, opposite direction, and the second mode of the calculator above does it.
Both of those are different from “is 7,919 prime?”. That is a primality test, it involves no counting whatsoever, and the prime calculator settles it for a single number in a few divisions. Keep the three apart: testing asks about one number, counting asks about a range, indexing asks about a position.
Approximating π(x) is where the prime number theorem earns its name — and where the version most people quote turns out to be the weak one. x / ln x is the headline result. The offset logarithmic integral Li(x) = ∫₂ˣ dt/ln t is the same idea done properly, and the difference is not subtle:
| x | π(x) | x / ln x | Miss | Li(x) | Miss |
|---|---|---|---|---|---|
| 10³ | 168 | 145 | −23 | 177 | +9 |
| 10⁴ | 1,229 | 1,086 | −143 | 1,245 | +16 |
| 10⁵ | 9,592 | 8,686 | −906 | 9,629 | +37 |
| 10⁶ | 78,498 | 72,382 | −6,116 | 78,627 | +129 |
| 10⁷ | 664,579 | 620,421 | −44,158 | 664,917 | +338 |
| 10⁹ | 50,847,534 | 48,254,942 | −2,592,592 | 50,849,234 | +1,700 |
At a billion, x / ln x is out by two and a half million primes. Li(x) is out by 1,700 — a relative error of 0.003%. Li also overshoots where x / ln x undershoots, which is a real result rather than a coincidence: Li(x) > π(x) for every x anyone has ever checked, though Littlewood proved in 1914 that the sign flips infinitely often somewhere far above where we can compute. The prime-counting function article on Wikipedia carries the exact values much further, and OEIS A000040 is the canonical list of the primes themselves.
The Jump to the Next Prime Is Not the Jump from the Last One
Around p₁₀₀₀ = 7,919 the average gap is ln(7,919) ≈ 9. Look at the actual neighbours and neither side matches: 7,907 → 7,919 is a jump of 12, and 7,919 → 7,927 is a jump of 8. The average is a statement about millions of primes at once, not about the two on your screen.
Small gaps cluster. Below 1,000 there are 35 twin-prime pairs — primes exactly two apart, like 641 and 643 — which is roughly one pair for every five primes in that range. Large gaps arrive late and dramatically. No gap of 100 or more occurs anywhere below 370,261, and when it finally shows up it is a gap of 112, running clean from 370,261 to 370,373. The largest gap anywhere under a million is 114, the stretch of 113 consecutive composite numbers that starts just after 492,113.
That has a direct practical consequence. If a program needs “a prime near 500,000” and only searches 20 numbers ahead, it will sometimes find nothing — because below a million you may have to walk more than a hundred steps. Search a window of at least 150 and you are safe in that range.
The Off-by-One That Ruins Half the Answers
Three conventions collide here, and each one shifts the answer by exactly one position.
- p₁ = 2, not 1. The number 1 was still being listed as prime into the early 1900s. It was dropped so that unique factorisation stays true — allow 1 and every number has infinitely many factorisations. So the 1st prime is 2, the 4th is 7, and any list that starts at 1 is permanently one place out.
- Zero-based versus one-based indexing. Mathematicians count from p₁; arrays count from 0. In a Python list of primes,
primes[1000]is 7,927 — the 1001st prime, not the 1000th. - π(x) is inclusive. π(7,919) = 1,000 because 7,919 itself counts. π(7,918) = 999. A specification that says “primes below x” may or may not mean the same thing, so check before you trust the number.
Project Euler’s problem 7 is a good stress test of all three: it asks for the 10,001st prime, and the answer is 104,743. The 10,000th is 104,729. One position apart, 14 integers apart — and a great many wrong submissions are simply that gap.
When You Actually Need a Prime by Position
Indexing primes sounds academic until you need a prime that is reproducible rather than merely convenient. A few places it comes up:
- Hash table sizing. Open-addressing tables behave badly when the modulus shares factors with the keys, so implementations grow to the next prime past a target size. “The next prime after 1,000,000” is 1,000,003 — count mode gives it directly.
- Reproducible test data. “The 500th prime” is a spec anyone can verify; “a random prime near 3,500” is not. Indexed primes make fixtures portable across languages.
- Competition and puzzle answers. Project Euler, Advent of Code and most coding-interview prime questions are phrased by position, not by value.
- Sanity-checking factorisations. If a prime factor calculator hands you a factor you did not expect, checking its position tells you instantly whether it is a small everyday prime or something far out in the tail.
Two related pages sit next door. Primes of the special shape 2ᵖ − 1 are indexed by their exponent rather than their position in the ordinary list, which is why the Mersenne prime calculator counts differently — the 52nd known Mersenne prime is nowhere near the 52nd prime. And if you only want the primes that divide a specific number rather than the primes at a specific rank, the prime factorization calculator is the faster route.
