The Sieve of Eratosthenes

What just happened?

The Sieve of Eratosthenes writes out the numbers 2, 3, 4, …, N, and then crosses out the multiples of each prime found — first 2 (4, 6, 8…), then 3 (6, 9, 12…), then 5, 7… Whatever is left uncrossed are the primes. A simple, mechanical recipe devised around 240 BC by Eratosthenes of Cyrene.

Why is it enough to sieve up to $\sqrt{N}$?

Every composite number $n$ has a prime divisor no greater than $\sqrt{n}$:

If both factors were greater than $\sqrt{n}$, their product would exceed $n$ — a contradiction. That is why every composite number is crossed out by some prime $p\le\sqrt{N}$ and there is no need to sieve further. This is the key to the algorithm’s efficiency.

There are infinitely many primes (Euclid, ~300 BC):

In the “Elements” (Book IX) Euclid proves this elegantly by contradiction. Suppose there are finitely many primes: $p_1, p_2, \ldots, p_k$. Consider the number:

The number $Q$ is not divisible by any of the $p_i$ (a remainder of 1 always stays). So either $Q$ is itself prime, or it has a prime divisor not on the list — in both cases there is a prime we did not include. A contradiction. The set of primes is therefore infinite: $|\{p : p \text{ prime}\}| = \infty$.

They thin out, but never end

Among the successive natural numbers the primes appear more and more rarely — their density $\pi(N)/N$ steadily decreases (visible on the bar to the right). Even so, they are never exhausted: you can always find the next one.

Why this matters for your exam:

The primes are the “building blocks” of all natural numbers — every natural number has a unique factorization into primes (the fundamental theorem of arithmetic). The Sieve of Eratosthenes and Euclid’s proof are classic school topics, and the primes are the foundation of modern cryptography (e.g. the RSA system bases its security on the difficulty of factoring large numbers into primes).

Remember: the Sieve of Eratosthenes crosses out the multiples of the primes up to $\sqrt{N}$ — because every composite number has a prime divisor $\le\sqrt{n}$. There are infinitely many primes (Euclid), although their density decreases.