Prime Numbers and the Sieve of Eratosthenes
A prime has exactly two divisors, 1 and itself. Learn why primes never run out, how the ancient Sieve of Eratosthenes finds them, and why they secure the internet.
A prime number is a whole number greater than 1 whose only divisors are 1 and itself. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. A number greater than 1 that is not prime is called composite. The number 2 is the only even prime, and 1 is deliberately excluded so that every integer factors into primes in exactly one way, as the fundamental theorem of arithmetic states. Primes are the building blocks of the integers, and one of the oldest algorithms for finding them still carries the name of a Greek scholar of the third century BC.
How does the Sieve of Eratosthenes work?
Eratosthenes of Cyrene (about 276 to 194 BC), chief librarian at Alexandria and the man who estimated the size of the Earth, described a way of finding primes by crossing out composites. To find every prime up to n:
- List the integers from 2 to n.
- Take the smallest number that is not crossed out. It is prime.
- Cross out its multiples, starting at its square, because smaller multiples were already removed by smaller primes.
- Repeat from step 2 until the next prime's square is larger than n.
Everything left is prime. For n equal to 30, you cross out multiples of 2, 3, and 5; the next prime, 7, has a square of 49, which is beyond 30, so you stop. What remains is 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29.
function sieve(n):
is_prime = array of n+1 values, all true
is_prime[0] = is_prime[1] = false
for p from 2 while p * p <= n:
if is_prime[p]:
for m from p * p to n step p:
is_prime[m] = false
return every p where is_prime[p] is true
The sieve runs in O(n log log n) time and uses O(n) memory, which is very close to linear (see Big O notation). Segmented versions work through huge ranges in blocks that fit in cache. For testing whether one very large number is prime, programmers use other methods such as probabilistic primality tests instead of a sieve.
Are there infinitely many primes?
Yes. Euclid proved it around 300 BC in Book IX of the Elements. Suppose the primes were a finite list. Multiply them all together and add 1. The result leaves remainder 1 when divided by any prime on the list, so none of them divides it. But the new number is either prime itself or has a prime factor, and in both cases there is a prime missing from the list. The assumption must be false.
How common are primes?
The prime number theorem, proved independently by Jacques Hadamard and Charles de la Vallée Poussin in 1896, says that the number of primes up to x is approximately x divided by the natural logarithm of x. There are 25 primes below 100, 168 below 1,000, and 78,498 below one million. Primes thin out slowly but never stop. Their fine-grained distribution is tied to the zeros of the Riemann zeta function, and the Riemann hypothesis would sharpen the error in that estimate.
Several simple questions remain open. The twin prime conjecture says there are infinitely many pairs such as 11 and 13 that differ by 2. Goldbach's conjecture says every even number greater than 2 is the sum of two primes, and computers have checked it to enormous limits without a counterexample. In 2013 Yitang Zhang proved that infinitely many pairs of primes differ by less than 70 million, and later work lowered that bound to 246.
What are the largest known primes?
The record holders are Mersenne primes, primes of the form 2p − 1, searched for by volunteers in the Great Internet Mersenne Prime Search. The largest known, found in October 2024 by Luke Durant using cloud GPUs, is 2136279841 − 1, a number with 41,024,320 digits. Mersenne numbers are favoured because a fast special-purpose test, the Lucas–Lehmer test, can check them.
Why do primes matter?
Multiplying two large primes is easy, but recovering them from the product appears to be extremely hard for classical computers. That asymmetry underlies RSA and much of public-key cryptography, where keys are built from primes hundreds of digits long, and where Euler's totient function is used to compute the private key. A large quantum computer running Shor's algorithm could factor such products quickly, which is why new cryptographic standards are being introduced. Primes also appear in hash table sizes, where a prime number of buckets helps spread keys evenly, and in nature: some periodical cicadas emerge on 13- and 17-year cycles, which may help them avoid synchronising with predators.
Tags
algorithms cryptography history of mathematics number theory prime numbers