Prime Sieve & Ulam Spiral

Watch the Sieve of Eratosthenes eliminate composites, or see primes on an Ulam spiral.

Worked example — Prime Sieve & Ulam Spiral

π(100)	25 primes
N / ln N	21.7(13.1% error)
Li(N)	29.1(16.3% error)
Twin pairs	8 pairs
Max gap	8

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — Prime Sieve & Ulam Spiral

The panel prints two different kinds of number and it is worth separating them before reading anything else. π(N) is a count — how many primes the sieve actually left standing, 25 at N = 100 and 95 at N = 500, exact and not rounded. The two rows beneath it are estimates of that same count. The Prime Number Theorem is the claim that one of them gets the ratio right in the limit; it is not a claim that it gets the number right. Those are very different promises, and the error column is where the difference lives.

What each symbol means

N: the ceiling you sieve up to, and the only input. The slider runs to 10000.
π(N): the number of primes not exceeding N. Counted, not estimated — it is however many cells the sieve failed to strike out.
N / ln N: the simplest estimate of that count. On every N this slider reaches it is below the truth.
Li(N): the logarithmic integral ∫₂ᴺ dt/ln t, a sharper estimate. On every N this slider reaches it is above the truth.

Where the formula comes from

The sieve never asks whether a number is prime. It starts at 2 and strikes out every multiple of 2, moves to the next number still standing, strikes out every multiple of that, and repeats. Primality is not tested; it is what is left over.
You only have to strike multiples of primes up to √N. If a number n ≤ N is composite then n = a·b with a ≤ b, so a ≤ √n ≤ √N — every composite has a factor at or below the square root, and was therefore already struck when that factor had its turn. Sieving to 100 needs only the passes for 2, 3, 5 and 7.
Count the survivors and you have π(N) exactly. This is why the top row is a fact and the two below it are opinions: the sieve produces the count as a by-product of finishing.
Now compare. The Prime Number Theorem says π(N) · ln N / N → 1 as N grows. Note what that does not say: a ratio tending to 1 permits the percentage error to stay large for an extremely long time, and the next row shows exactly that happening.

How to read what you see

Read the two error figures as a race and change N. At N = 100 the crude estimate is winning: 13.1% against Li’s 16.3%. Go to N = 200 and it reverses — 17.9% against 6.9% — and it never reverses back. But the real thing to watch is what N/ln N fails to do. Across two orders of magnitude its error reads 14.8%, 13.1%, 15.3%, 13.8%, 12.2%: it wanders, and it barely improves. Li over the same span goes 16.3% to 2.8%. Both estimates satisfy the Prime Number Theorem; only one of them is any use at the sizes you can see. The signs are just as consistent — N/ln N sits under the count at every N here, Li sits over it.

Assumes: That N is small enough to sieve outright: the count is exact because every number up to N is actually held and struck, which is why the ceiling is 10000 rather than 10¹⁰. The error percentages are taken against π(N), so they measure the estimates and never the count.
Breaks when: Li(N) > π(N) at every N this page can reach, which makes it look like a law. It is not. Littlewood proved in 1914 that the difference changes sign infinitely often, so there are values of N where Li undercounts — and in the century since, nobody has exhibited a single one. Bays and Hudson pinned the first crossing below about 1.4×10³¹⁶ in 1999, and nobody has narrowed it since. So this page shows you a pattern that is provably not universal, and no setting of the slider can reach the counterexample. That gap between what you can see and what is true is the honest shape of this subject.

The thinning you watch in the grid is the part nobody can prove 🖖

The precise distribution of primes is controlled by the zeros of the Riemann zeta function ζ(s). All 10¹³ known non-trivial zeros lie on the critical line Re(s) = 1/2. Proving this for all zeros would give the sharpest possible prime-counting bounds — and win a $1 million Millennium Prize. As of 2025, it is unproved.

Sieving instead of testing 🖖

The Sieve of Eratosthenes finds primes by elimination rather than by testing each number. Start at 2, cross out every multiple, jump to the next surviving number, and repeat; whatever is never crossed out is prime. The clever shortcut: to sieve all numbers up to n, you only need to remove multiples of primes up to √n. So sieving everything below 100 requires crossing out multiples of just 2, 3, 5 and 7.

Ulam's bored doodle 🖖

In 1963 the mathematician Stanisław Ulam, bored during a talk, scribbled the integers in a square spiral and shaded the primes — and startlingly clear diagonal streaks appeared. Those diagonals trace prime-rich quadratics like Euler's n² + n + 41, which yields a prime for every n from 0 to 39. Why certain diagonals stay so dense is still not fully understood, which is why the pattern keeps fascinating number theorists.

Problems solved in full

Sieving the 25 primes below 100 by hand 5 steps
There are 25 primes below 100. Sieve them by hand — it takes less work than you would guess — and then test the prime number theorem on a sample far too small for it.
1. The sieve's saving is the reason it is worth a name. If n ≤ 100 is composite it factors as ab, and the smaller factor cannot exceed √100 = 10. So striking out the multiples of every prime up to 10 removes every composite there is: four primes do the entire job.
  
  $n \leq 100 composite ⟹ n = ab with min (a, b) \leq 100 = 10$
2. Cross out the multiples of 2, 3, 5 and 7, each starting at its own square because everything below that has already gone. Twenty-five numbers survive.
  
  $strike multiples of 2, 3, 5, 7 from 4 upward ⟹ π (100) = 25$
3. The prime number theorem says the count is asymptotically N/ln N. At N = 100 that is 21.7.
  
  $π (N) \sim \frac{N}{ln N} : \frac{100}{ln 100} = \frac{100}{4.6052} = 21.7$
4. It is 13% low, which is what an asymptotic result is entitled to be at 100. Read the other way round it is still useful here: the density of primes near N is 1/ln N, so roughly 22% of numbers near 100 are prime against 7.2% near a million. Primes thin out logarithmically, which is very slowly indeed.
  
  $\frac{25 - 21.7}{25} = 13.1%, \frac{1}{ln 100} = 21.7% vs \frac{1}{ln 1 0 ^{6}} = 7.2%$
5. The gaps agree. The mean gap below 100 is 100/25 = 4, and the largest is 8 — the run from 89 to 97. Twice the average, and no worse.
  
  $mean gap = \frac{100}{25} = 4, largest = 97 - 89 = 8$
Answer

The sieve gives π(100) = 25 and the tool prints the estimate at 21.7, 13.1% low. That error is not the theorem failing; it is the theorem's rate of convergence made visible, and the convergence is famously unhurried — push N to 10 000, four orders of magnitude up, and the estimate is still low by double digits. What holds at every scale is the density reading. One number in 4.6 near 100 is prime, one in 13.8 near a million, and because the logarithm grows so slowly the primes never run out and never even become properly rare.

$π (100) = 25 from four primes; \frac{N}{ln N} = 21.7 (13.1% low)$
The obvious estimate for 8 twin pairs below 100 6 steps
The panel counts 25 primes below 100 and 8 twin pairs. The first number has a famous estimate that gets within 13%. Try the obvious estimate for the second — and watch it miss by a factor that has a name.
1. Take the printed count and the printed estimate as the starting point: near N a number has roughly a 1/ln N chance of being prime, and at N = 100 that is about 0.2171.
  
  $π (100) = 25, \frac{N}{ln N} = \frac{100}{4.6052} = 21.7$
2. Now assume n and n+2 are independent. If each is prime with probability 1/ln N, both are prime with the square of that.
  
  $P_{1} \approx \frac{1}{ln N} = 0.2171 ⟹ P_{2} \approx P_{1}^{2} = \frac{1}{( ln N ) ^{2}}$
3. Multiply by N and compare with the tool. The estimate says 4.72 twin pairs below 100; the sieve found 8. The estimate is not slightly off — it is short by 40%.
  
  $N P_{2} = \frac{100}{21.208} = 4.72 ⟷ π_{2} (100) = 8$
4. Independence is the false step, and one prime shows why. Take any odd prime p: a random n is killed by p one time in p, but the pair is killed whenever n or n+2 is divisible by p, which is two residues out of p — so the survival rate is (p−2)/p, not the square of (p−1)/p that independence assumed.
  
  $p > 2 : n \equiv 0 \lor n + 2 \equiv 0 (mod p) ⟹ \frac{p - 2}{p} \neq = (\frac{p - 1}{p})^{2}$
5. Multiply that correction over every odd prime and it converges to a constant. Twice it is 1.3203, and applying it lifts the estimate to 6.23.
  
  $2 C_{2} = 2 p > 2 \prod \frac{p ( p - 2 )}{( p - 1 ) ^{2}} = 1.3203 ⟹ 1.3203 \times 4.72 = 6.23$
6. Still short of 8 at N = 100 — the estimate is asymptotic and 100 is a small number. It converges: 156 pairs predicted below 10⁴, 6917 below 10⁶.
  
  $N = 1 0^{4} : 156 N = 1 0^{6} : 6917$
Answer

The naive count is 4.72, the corrected one 6.23, and the truth is 8 — and the correction factor 1.3203 is an infinite product over the primes. That constant is the price of assuming independence where there is none, and it is the shape of nearly every hard question in the subject: the primes are random enough that a heuristic works, and structured enough that it needs a correction nobody can derive from first principles. The twin prime conjecture is the statement that this estimate never runs out of pairs, and it is still open.

$π_{2} (N) \sim 2 C_{2} \frac{N}{( ln N ) ^{2}}, 2 C_{2} = 1.3203 : 4.72 \to 6.23 ⟷ 8$

References (4)

Why the page’s most convincing pattern is not a law — the difference changes sign infinitely often: J. E. Littlewood, "Sur la distribution des nombres premiers." Comptes Rendus de l’Académie des Sciences, Paris 158, 1869–1872, 1914. No DOI: the volume predates them.
How far the first sign change has been pinned down, and where the 1.4×10³¹⁶ comes from: C. Bays & R. H. Hudson, "A new bound for the smallest x with π(x) > li(x)." Mathematics of Computation 69, 1285–1296, 1999.
How far the Riemann hypothesis has actually been verified — note this is a bound on height, a different measure from a count of zeros: D. J. Platt & T. S. Trudgian, "The Riemann hypothesis is true up to 3·10^12." Bulletin of the London Mathematical Society 53, 792–797, 2021.
The prize, and its official problem statement: Clay Mathematics Institute, Millennium Prize Problems — the Riemann Hypothesis.

By the 42Math team · Updated 2026-06-20

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Mathematics lessons →

Example problems

Small (100) - Sieve to 100 and the crude estimate wins: N/ln N gives 21.7, out by 13.1%, while Li(100) = 29.1 is out by 16.3%. This is the only preset where that happens. Go to 500 and Li's error falls to 6.2% while N/ln N sits at 15.3% and stays there.
Medium (500) - 95 primes below 500, in 24 twin pairs, with a largest gap of 14 — the stretch from 113 to 127 with nothing prime inside it. That record then holds until 523, where a gap of 18 opens. A record gap does not grow steadily with N; it waits.
Cool Columns - 154 primes below 900, in 35 twin pairs. Carry on to 1000 and you pick up 14 more primes and not one new twin pair: the last is 881 and 883. Twins thin out faster than primes do, and whether they ever stop is still open.
Ulam 400 - The same 78 primes as grid mode, re-seated on a square spiral. Nothing about the numbers changed — the diagonal bands come from where the spiral puts each integer, which is why a picture can suggest a pattern the arithmetic has not confirmed.
PNT (1000) - π(1000) = 168. N/ln N gives 144.8, out by 13.8%; Li(1000) gives 177.0, out by 5.3%. Both satisfy the Prime Number Theorem, and at every N this tool reaches only one of them is any use — and Li sits above the true count every time.