A prime number is a natural number greater than 1 that has no divisors other than 1 and itself.

$$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, \ldots$$

Numbers that aren’t prime (and are greater than 1) are called composite. Every composite number can be written as a product of smaller numbers: $12 = 4 \times 3$, $15 = 5 \times 3$. Primes can’t — they’re the atoms of multiplication.

Why primes matter

Primes are the building blocks of all natural numbers. Every number greater than 1 is either prime or can be broken down into a product of primes — and that breakdown is unique (up to reordering). This is the Fundamental Theorem of Arithmetic, and it’s the reason primes are central to number theory.

$60 = 2 \times 2 \times 3 \times 5 = 2^2 \times 3 \times 5$

No other combination of primes gives 60. This uniqueness is what makes prime factorisation useful — it’s a fingerprint for every number.

The Sieve of Eratosthenes

The oldest algorithm for finding primes, invented around 240 BC. Start with all numbers from 2 onwards. The smallest unmarked number is prime — mark it, then cross out all its multiples. Repeat.

How many primes are there?

Infinitely many. Euclid proved this around 300 BC, and the proof is one of the most beautiful in mathematics.

Euclid’s proof: Suppose there are only finitely many primes: $p_1, p_2, \ldots, p_n$. Consider the number

$$N = p_1 \times p_2 \times \cdots \times p_n + 1$$

$N$ is not divisible by any of the primes $p_1, \ldots, p_n$ (dividing by any of them leaves remainder 1). So either $N$ is itself prime, or it has a prime factor not in our list. Either way, we’ve found a prime that wasn’t in the list. Contradiction. ∎

This is a proof by contradiction — assume the opposite of what you want to prove, show it leads to an impossibility.

How common are primes?

Primes thin out as numbers get larger, but they never stop entirely. The Prime Number Theorem (proved in 1896) says that the number of primes up to $N$ is approximately

$$\pi(N) \approx \frac{N}{\ln N}$$

where $\pi(N)$ is the prime-counting function (not the constant $\pi$). Among the first 1,000 numbers, about 168 are prime. Among the first million, about 78,498. The proportion drops, but never reaches zero.

Primes and patterns

Primes resist easy patterns. There’s no simple formula that generates all primes and only primes. But there are striking regularities:

• Twin primes: Pairs like (11, 13), (17, 19), (29, 31) — primes separated by 2. It’s conjectured there are infinitely many, but this remains unproven.
• Primes in arithmetic progressions: Dirichlet (1837) proved that for any two coprime integers $a$ and $N$, there are infinitely many primes of the form $a + kN$. Primes are spread evenly across residue classes.
• Gaps: The gap between consecutive primes can be arbitrarily large (consider $n! + 2, n! + 3, \ldots, n! + n$ — all composite). But primes keep coming back.

The deepest patterns in prime distribution connect to the Riemann zeta function — a bridge between primes and analysis that we’ll reach through infinite series.