Sieve of Eratosthenes

Mark composite multiples to reveal every prime up to N

Find primes in one shared pass

Begin with every integer from 2 through N unmarked. The next unmarked value is prime. Mark all of its multiples as composite, then continue to the next unmarked value. The values never marked are exactly the primes.

Start at p squared

Multiples smaller than p^2 already contain a smaller prime factor and were marked earlier. Once p^2 > N, every composite at most N has already been reached through a factor at most sqrt(N), so all remaining unmarked values can be confirmed together.

The number grid runs to 30. Green cells are confirmed primes, gray cells are composite, amber marks the current prime, and newly crossed-out multiples flash red.

Lay out 1 through 30; 1 is neither prime nor composite, and all larger values start unmarked.

1function sieve(n: number): number[] {
const isComposite = new Array(n + 1).fill(false);   // initially unmarked
const primes: number[] = [];
for (let p = 2; p <= n; p++) {
  if (!isComposite[p]) {                            // unmarked p is prime
    primes.push(p);
    for (let m = p * p; m <= n; m += p)             // mark multiples of p from p^2
      isComposite[m] = true;
  }
}
return primes;                                      // remaining unmarked values are prime
12}

Range1..30

Confirmed primes0

1 / 9

Near-linear preprocessing

The harmonic sum over prime multiples gives O(N log log N) time and the marking array uses O(N) space. The sieve is ideal when many later queries need the same bounded prime table.

Invariant: before processing prime p, every composite below p^2 has already been marked by a smaller prime factor.

Continue the number-theory path with the remainder invariant in the Euclidean Algorithm.

Algorithm Visualizer

Sieve of Eratosthenes

Find primes in one shared pass

Start at p squared

Near-linear preprocessing