A prime number is an integer $p > 1$ whose only positive integer divisors are $1$ and $p$ itself; an integer greater than $1$ that is not prime is called composite because it factors as $a \cdot b$ with $1 < a, b < n$. In Book VII, Definitions 11 and 13 of the Elements (c. 300 BCE), Euclid states this in geometric language: a prime number is "measured by a unit alone," whereas a composite number is "measured by some number."

Our goal is to prove Book IX, Proposition 20 of Euclid's Elements: "Prime numbers are more than any assigned multitude of prime numbers" — in modern notation, the set of all primes $\mathbb{P}$ is infinite ($|\mathbb{P}| = \infty$). Rather than trying to write down a formula that generates every prime in order, Euclid shows how to take any finite collection of primes and construct at least one more prime missing from that collection.