Assume every number is prime, then for each surviving prime p strike out its multiples starting at p². Whatever survives is prime. Runs in O(n log log n).
step 0
Number grid (2 … 50)
unknown current prime p being struck composite (struck) confirmed prime
State
current p—
striking—
start at p²—
stop whenp² > n
π(n) so far0
Primes found
Press Step to begin. We assume every number from 2 to n is prime, then strike out the multiples of each prime in turn.
How to read this animation
Step advances one action at a time: confirming a prime, or striking one multiple.
Run auto-plays at the chosen speed; press again to pause.
Edit n (2–120) and the grid rebuilds; the prime list and π(n) update live.
The current prime p is outlined in blue; the cell being struck flashes red; confirmed primes glow green; struck composites fade with a line through them.
Watch how striking always begins at p² — smaller multiples of p were already struck by smaller primes.
# Sieve of Eratosthenes
isPrime[0..n] = true
isPrime[0] = isPrime[1] = false
for p = 2; p*p <= n; p++:
if isPrime[p]: # p survived -> primefor m = p*p; m <= n; m += p:
isPrime[m] = false # strike multiple# survivors are the primes; cost O(n log log n)
Self-contained visualization. Each composite is struck by at least one prime factor; primes are never struck because their own striking starts at p² > p.
The outer loop stops once p² > n because every composite ≤ n has a prime factor ≤ √n. See junior.md and professional.md for the proof and the O(n log log n) analysis.