The Oldest Algorithm
The Sieve of Eratosthenes, dating to roughly 240 BC, is one of the oldest known algorithms still in practical use. Eratosthenes of Cyrene — the same polymath who measured the Earth's circumference — devised a simple method: write down all numbers, then systematically cross out multiples of each prime. What remains is the complete list of primes.
How the Sieve Works
Start with 2, the smallest prime. Cross out 4, 6, 8, 10... (all multiples of 2). The next uncrossed number is 3 — cross out 9, 15, 21... (multiples of 3 not already crossed). Continue with 5, 7, 11... You only need to sieve up to the square root of your maximum number, because any composite number must have a factor less than or equal to its square root.
The Distribution of Primes
Primes become sparser as numbers grow, but they never run out — Euclid proved this around 300 BC. The Prime Number Theorem, proved independently by Hadamard and de la Vallee Poussin in 1896, quantifies the thinning: roughly 1 in every ln(N) numbers near N is prime. The exact distribution connects to the Riemann Hypothesis, the greatest unsolved problem in mathematics.
Primes and Cryptography
Modern internet security rests on prime numbers. RSA encryption uses the product of two large primes as a public key. Multiplying two 300-digit primes is easy, but factoring the result back into its prime components would take longer than the age of the universe with current algorithms. This asymmetry is the foundation of secure digital communication.