What you're seeing
Write the numbers from 1 to n in a grid. The first uncrossed number above 1 is 2 — it's prime, so we cross out every multiple of 2. The next still-uncrossed number is 3 — prime — cross out its multiples. Then 5, then 7, and so on. Any number that gets crossed had a smaller prime factor; any number that's never crossed has none, so it's prime. Watch the orange waves of multiples fall away each round until only the primes remain green.
The rule
sieve(n):
mark all of 2..n as prime
for p = 2, 3, 4, … while p·p ≤ n:
if p is still marked prime:
for m = p², p²+p, p²+2p, … ≤ n:
mark m as composite
the still-marked numbers are the primes
Two tricks make it fast: start crossing at p² (smaller multiples already fell to smaller primes), and stop sieving once p² > n (anything composite ≤ n must have a factor ≤ √n).
The invariant
The loop maintains a clean two-part fact: a number is still marked prime if and only if it has no prime factor smaller than the current p. So when the loop advances to a p that is still marked, p has no smaller prime factor — which is the definition of being prime. Crossing out p's multiples then restores the invariant for the next step, and crucially it can never cross out a prime, because a prime has no factors to be a multiple of. Once p² > n the invariant says every remaining marked number is free of all factors ≤ √n, hence prime — so the sweep can stop. The survivors are exactly the primes; no primality test is ever performed, only crossing-out.
The cost
The work to cross out one prime's multiples is n/p, and summing n/p over the primes p ≤ n gives n·(sum of reciprocals of primes) ≈ n·ln ln n — astonishingly close to linear. That blows away testing each number for primality separately. The cost is the O(n) bit array; segmented sieves break that into cache-sized chunks to push n into the billions.
In the wild
The sieve is the standard way to enumerate primes in bulk — precomputing prime tables for number theory and competitive programming, factoring via smallest-prime-factor tables, and as a subroutine when an algorithm needs "all primes up to N." It's over 2000 years old (Eratosthenes of Cyrene, ~200 BC) and still the method of choice; modern variants (the sieve of Atkin, wheel factorization, segmented sieves) trim constants but keep the idea. For testing a single large number, though, you'd reach for a probabilistic test like Miller–Rabin instead — sieving is for generating many primes, not checking one.
Try this
Step through the first few rounds and notice how quickly the grid empties: the 2s and 3s alone strike most composites, and later primes find fewer and fewer new multiples to cross. Notice too that sieving stops well before n — once a prime exceeds √n, every survivor is already guaranteed prime.
References
- Eratosthenes of Cyrene (c. 200 BC); described by Nicomachus, Introduction to Arithmetic. The classical sieve.
- Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §31 (Number-Theoretic Algorithms). MIT Press, 2022.
- Crandall, R. & Pomerance, C. Prime Numbers: A Computational Perspective, 2nd ed., §3 (sieving, segmented sieves). Springer, 2005.