1
Crossing out is cheaper than testing
Testing each number separately repeats work. The sieve marks each composite once per distinct prime factor and no more.
Lesson · Number Theory and Cryptography · Divisibility
The Sieve of Eratosthenes
The oldest algorithm still in use. It finds every prime up to n by removing multiples, stops at √n for the reason “Primes and Unique Factorisation” gave, and costs far less than testing each number separately.
for each prime p ≤ √n: cross out 2p, 3p, … — starting at p²
whatever is left uncrossed is prime
start at p²: smaller multiples were removed by smaller primes
cost ≈ n log log n operations
One pass per small prime
Core ideas
What this lesson establishes
The sieve is the standard example of an algorithm that beats the obvious approach by reorganising the work.
2
Start at p²
Multiples of p below p² have a smaller prime factor and were already crossed out. Starting at 2p is correct and wasteful.
3
Stop at √n
After sieving by every prime up to √n, anything uncrossed has no factor below its square root and is prime, by “Primes and Unique Factorisation”'s bound.
The material
The sieve
The algorithm, its two optimisations, and its cost.
SIEVE(n):
mark 2 … n as candidates
for p = 2, 3, 4, … while p·p ≤ n:
if p is still a candidate: # then p is prime
for q = p², p²+p, p²+2p, … ≤ n:
cross out q
the surviving candidates are the primes ≤ n
Two things make it efficient. The outer loop stops at √n because anything surviving that far has no prime factor below its own square root. The inner loop starts at p² because a multiple kp with k < p has the prime factor k or a factor of it, and was removed earlier.
Theorem · Correctness
After the sieve, an integer m in 2, …, n is uncrossed if and only if it is prime.
A prime is never crossed out: it is only removed as a multiple kp with k ≥ p ≥ 2, so any crossed-out number is composite.
A composite m has a prime factor p ≤ √m ≤ √n by “Primes and Unique Factorisation”. When the outer loop reaches p, p is still a candidate (it is prime), and m = p·(m/p) with m/p ≥ p, so m ≥ p² and m is a multiple of p at or beyond p². It is crossed out.
□
Cost
The inner loop for prime p performs about n/p operations, so the total is roughly n Σ_{p ≤ √n} 1/p. The sum of reciprocals of primes up to x grows like ln ln x, giving Θ(n log log n) — very nearly linear, and log log n is under 5 for any n anyone will run.
Compare with testing each number by trial division: about √m divisions for each m, giving Θ(n^{3/2}/log n) overall. At n = 10⁶ the sieve does a few million operations and trial division does roughly a hundred million.
primes below n:
10 4
100 25
1 000 168
10 000 1 229
100 000 9 592
1 000 000 78 498 n/ln n predicts 72 382
The prime number theorem says the count is asymptotically n / ln n, and the table shows the approximation improving slowly. A better estimate is the logarithmic integral, which at 10⁶ gives 78 628 against the true 78 498.
Limits
The sieve finds all primes up to n and needs memory proportional to n. For the 1024-bit primes RSA needs, sieving is hopeless: there are more candidates than atoms in the universe. Those primes are found by testing random numbers with probabilistic tests such as Miller–Rabin, which decide primality without producing factors.
Interactive
Number theory workbench
Algorithms with their traces
Method
Running the sieve
One pass per prime, starting at its square.
1
List the candidates
2 through n. The number 1 is excluded from the start.
2
Take the smallest uncrossed number
It is prime, because nothing smaller divides it.
3
Cross out its multiples from p² upward
Smaller multiples already went. This is the optimisation that halves the work at small primes.
4
Stop when p² > n
Everything still uncrossed is prime, by the trial-division bound.
The sieve
Score 0 / 0Choose the answer you can justify.
Sieving to 30
√30 ≈ 5.5, so only 2, 3 and 5 need passes.
start 2 3 4 5 6 7 8 9 10 … 30
p = 2 cross 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30
p = 3 cross 9, 15, 21, 27 (6, 12, 18, 24, 30 already gone)
p = 5 cross 25 (10, 15, 20, 30 already gone)
p = 7 7² = 49 > 30 ⟹ STOP
surviving: 2 3 5 7 11 13 17 19 23 29 — 10 primes
Note the p = 3 pass started at 9, not 6, and the p = 5 pass at 25.
The p = 5 pass crossed out exactly one number. That is typical: nearly all the work happens at the smallest primes, which is why the total cost is n log log n rather than n log n.
Common mistakes
1
Sieving past √nPasses for larger primes remove nothing new. The bound is the same one that limits trial division.
2
Starting the inner loop at 2pCorrect but wasteful: those multiples have already been removed by smaller primes.
3
Expecting the sieve to scale to cryptographic sizesIt needs memory proportional to n. Finding a 1024-bit prime uses probabilistic testing, not sieving.
Check your understanding
✓
Finish when you can predict the passes and the stopping point.
Before sieving to 200, say which primes need passes and roughly how many numbers each will cross out. Then run it and compare — the prediction is the understanding.
Note: The sieve is over two thousand years old and is still the fastest way to enumerate the primes in a range. Modern variants (segmented sieves, the sieve of Atkin) improve the constants and the memory profile without changing the idea.