The site's third Number Theory entry, and a different kind of question from the first
two. Euclidean Algorithm and
Extended Euclidean Algorithm both start from two
specific numbers and ask how they relate. This one starts from a single bound n and asks a
different shape of question entirely: which numbers from 2 to n are prime — divisible by
nothing but 1 and themselves? Trial-dividing every candidate one at a time works, but it re-derives the
same information over and over. The sieve finds all of them in one coordinated sweep instead.
Eratosthenes of Cyrene described it around 240 BCE while running the Library of Alexandria — old enough that, like the plain Euclidean algorithm, it predates the concept of an algorithm by roughly two thousand years and still ships unmodified in production code today. The idea: write out every number from 2 to n: the first unmarked number is always prime (nothing smaller could have divided it, or it would already be marked). Cross out every multiple of it. Move to the next unmarked number and repeat. What survives uncrossed is exactly the set of primes.
Pick a bound and step through the sweep. 100 is large enough to see the pattern settle; 30 finishes in a handful of steps; 200 shows the grid getting sparser as primes thin out. Green cells are confirmed prime, faded cells are marked composite — everything else is still an open candidate until the final sweep step resolves it.
The correctness argument rests on one fact: a composite number always has a prime factor no
larger than its own square root. If m = a·b with both a, b > 1, they
can't both exceed √m — if they did, their product would exceed m. So the smaller
factor is always ≤ √m, and following that factor's chain down to a prime always lands on a
prime ≤ √m. That means the outer loop only ever needs to test candidates p from 2
up to ⌊√n⌋: any composite number ≤ n is guaranteed to have already been crossed out by one of
its prime factors in that range, well before the loop would reach it directly.
The second piece: when the loop reaches p and finds it still unmarked, p is
prime — every smaller number that could have marked it as a multiple would already have run. And once
p is confirmed prime, marking its multiples can start at p² rather than
2p: every smaller multiple 2p, 3p, …, (p-1)p has a factor smaller than
p and was already marked composite by that smaller prime on an earlier iteration. Starting at
p² doesn't change the final answer — it just skips redundant re-marking (quantified in
Pitfalls below).
for p in 2..⌊√n⌋:
if p is unmarked: # p is prime
for m in p², p²+p, p²+2p, ..., ≤ n:
mark m composite
# everything still unmarked from 2..n is primefunction sieve(n) {
const marked = new Array(n + 1).fill(false); // marked[i]: is i known composite?
const bound = Math.floor(Math.sqrt(n));
for (let p = 2; p <= bound; p++) {
if (marked[p]) continue;
for (let m = p * p; m <= n; m += p) marked[m] = true;
}
const primes = [];
for (let i = 2; i <= n; i++) if (!marked[i]) primes.push(i);
return primes;
}A strict < instead of <= in the outer loop bound silently drops
perfect squares of primes. It's tempting to write the bound as p * p < n instead of
p * p <= n — off by one, and easy to miss because it's usually harmless: for most n,
the last prime ≤ √n still gets tested either way. It only breaks when n is itself the square of
a prime, because then that exact prime is the one candidate the stricter bound excludes:
function sieveBuggy(n) {
const marked = new Array(n + 1).fill(false);
for (let p = 2; p * p < n; p++) { // bug: should be <=
if (marked[p]) continue;
for (let m = p * p; m <= n; m += p) marked[m] = true;
}
const primes = [];
for (let i = 2; i <= n; i++) if (!marked[i]) primes.push(i);
return primes;
}Checked directly against the correct version on every perfect square of a prime from 7² up to 19²: n = 49 (7²), 121 (11²), 169 (13²), 289 (17²), and 361 (19²) each come back with exactly one extra number in the buggy output — 49, 121, 169, 289, and 361 respectively, each falsely reported prime, because the one prime that would have marked it (its own square root) was never tested. Every other n in the checked range matched exactly. A demo or test suite that only tries "round" bounds like 100 or 1000 will never surface this — it takes an n that's exactly a prime squared to expose it.
Starting multiples at 2p instead of p² is still fully correct — just
measurably wasteful, not dramatically so. Unlike the
Euclidean algorithm's subtractive-vs-modulo gap (2 steps vs. 999,999 on the same input), this
optimization's payoff is real but modest, and it's worth reporting honestly rather than oversold. Counting
every composite-marking operation for both versions:
n=100 n=10,000 n=1,000,000
start at 2p: 113 17,991 2,197,839
start at p²: 104 16,981 2,122,048Roughly a 5% reduction across three orders of magnitude of n, not a change in asymptotic class — both are
still O(n log log n). The saved operations are exactly the multiples 2p, 3p, …, (p-1)p, which
the correctness argument above already shows were marked by a smaller prime earlier; re-marking an
already-marked cell is safe (idempotent) but pure waste.
O(n log log n) time, O(n) space — the count of primes up to n found in a single array
pass, versus testing each of the n candidates individually by trial division (each trial division costs up
to O(√n), for an O(n√n) total). The time bound follows from summing the per-prime cost
n/p over every prime p ≤ √n: that sum is n · Σ(1/p), and the sum of
reciprocals of primes up to x grows like log log x (Mertens' second theorem) — an extremely
slowly growing function that's under 4 even for x in the billions. In practice this makes the sieve one of
the fastest ways known to enumerate primes up to bounds in the tens of millions.
This page finds every prime up to a bound in one sweep, which is a different problem from deciding whether one specific, very large number is prime — trial division against a sieve doesn't scale once that number has hundreds of digits, the regime cryptography actually cares about. See Miller–Rabin Primality Test for that problem.
This site's guide, Choosing a Number Theory Algorithm, compares this entry against the other thirteen Number Theory entries side by side.