Visualize

Pattern visualizer

Sieve of Eratosthenes

Checking each number for primality on its own repeats the same divisions over and over. The sieve inverts that: assume everything is prime, then let each prime it confirms erase its own multiples in one sweep. Two details make it fast. A base whose cell is already crossed out is skipped, because its multiples were erased by the smaller prime that crossed it out. And each sweep starts at i * i, not 2 * i, because every smaller multiple of i carries a factor below i and is already gone. Once i * i passes n there is nothing left to erase, since a surviving composite would need two factors larger than the square root and their product would overshoot n. Animated on: n = 16 — list every prime from 2 up to n..

Erase multiples instead of testing divisibility

time O(n log log n)space O(n)step 1 / 16
2
[0]
3
[1]
4
[2]
5
[3]
6
[4]
7
[5]
8
[6]
9
[7]
10
[8]
11
[9]
12
[10]
13
[11]
14
[12]
15
[13]
16
[14]
line 2

Every number from 2 to 16 starts out assumed prime. Testing each one by dividing it costs a fresh scan per number; instead each prime we confirm will erase all of its own multiples in one sweep, so no number is ever tested — only crossed out.

Pseudocode
1FUNCTION sieve(n):
2  isPrime[2..n] <- TRUE
3  i <- 2
4  WHILE i * i <= n:
5    IF isPrime[i] = TRUE:
6      FOR j <- i * i TO n STEP i:
7        isPrime[j] <- FALSE
8    i <- i + 1
9  FOR k <- 2 TO n:
10    IF isPrime[k] = TRUE:
11      APPEND k TO primes
12  RETURN primes

← / → step · space play · Home restart

Where to practice Math

Practice Math problemsAll Math problemsBack to roadmap