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 prime
function 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,048
Roughly 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.
The Complexity section below calls this "one of the fastest ways known to enumerate primes up to bounds
in the tens of millions" — true in direction, but with no number behind it, and the demo above caps out at
n=500, nowhere near "tens of millions." Measured directly here: this page's own shipped sieve
function above against a textbook trial-division prime counter (for each candidate, test divisibility by
every integer from 2 up to that candidate's own square root, stopping at the first factor found) —
correctness cross-checked first, both returning identical prime counts for every n from 100 to 100,000, and
sieve's own count at n=10,000,000 matching the well-known value π(10,000,000) =
664,579 exactly.
Wall-clock, in Node on this machine:
n sieve trial division ratio
10,000 0.1 ms 0.6 ms 5.4×
100,000 1.8 ms 13.4 ms 7.3×
1,000,000 22.2 ms 333.0 ms 15.0×
10,000,000 407.9 ms 8,602.4 ms 21.1×
30,000,000 1,395.4 ms 40,650.9 ms 29.1×
The gap doesn't just hold at "tens of millions," it widens as n grows — unlike most
crossover-style claims elsewhere on this site, where an early advantage narrows or reverses at realistic
scale, this one gets more lopsided the bigger n gets, exactly as the two time bounds predict
(n log log n grows barely faster than linear; n√n doesn't).
Counting the operation each approach actually spends its time on — every composite-marking array write for the sieve, every modulo check for trial division — shows the same direction but an even wider gap:
n sieve marks trial mod-checks ratio
10,000 16,981 117,527 6.9×
100,000 193,078 2,745,694 14.2×
1,000,000 2,122,048 67,740,404 31.9×
10,000,000 22,850,051 1,746,210,133 76.4×
30,000,000 70,634,109 8,332,398,189 118.0×
The operation-count ratio (118× at n=30,000,000) outpaces the wall-clock ratio (29.1× at the
same n) by about 4× — each individual trial-division mod-check is cheaper in practice than each
sieve array write, since the sieve's writes jump around memory by stride p while trial
division's mod-checks stay in a tight, cache-friendly inner loop. The constant-factor edge favors trial
division's own operation, it's just vastly outnumbered: sieve marks grow like n log log
n (barely faster than linear), while trial-division checks grow close to n√n /
log n (the average early-exit on a composite's smallest factor saves some, but primes themselves
always pay the full √n) — a gap in operation count wide enough to swallow the
per-operation disadvantage many times over.
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. See measuring against trial division above for what that bound
actually buys: a lead over trial division that widens, not narrows, from roughly 5× at n=10,000 to
nearly 30× at n=30,000,000.
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 fourteen Number Theory entries side by side.