The Sieve of Eratosthenes: Finding Primes the Ancient Greek Way

What if the most powerful tool in modern cryptography — the thing that keeps your bank transfers, private messages, and passwords safe — traces its origins to an ancient Greek librarian sitting in Alexandria around 240 BCE, sifting numbers by hand? The Sieve of Eratosthenes is exactly that: a beautifully simple algorithm for finding prime numbers, old enough to predate the fall of the Roman Republic, yet still running (in refined form) inside the software that secures the internet today.

The Concept

Prime numbers are the atoms of arithmetic. Every whole number greater than 1 is either prime — divisible only by 1 and itself — or composite, meaning it can be broken down into a product of primes. The number 12, for instance, is 2 × 2 × 3. The number 37 can't be broken down at all: it's prime.

This makes primes feel like the irreducible, indivisible building blocks of the number system. And for millennia, mathematicians have been obsessed with a deceptively simple question: which numbers are they?

The sieve answers that question for every number up to some limit N. Here's how it works, step by step:

1. Write out all the whole numbers from 2 to N. 2. Circle 2 — the first prime. Then cross out every multiple of 2 (4, 6, 8, 10, ...). These are all composite. 3. The next uncrossed number is 3. Circle it. Cross out every multiple of 3 (9, 15, 21, ...) — the ones not already crossed. 4. Next uncrossed: 5. Circle, cross out multiples. 5. Keep going until the prime you're working with exceeds the square root of N. At that point, everything still uncrossed is prime.

That's it. No fancy algebra, no recursion. Just systematic elimination.

The key insight is why you can stop at the square root of N. If a number n has a factor larger than √n, it must also have a factor smaller than √n — because factors come in pairs. So by the time you've sifted through all primes up to √N, every composite number remaining has already been crossed off by a smaller prime. Whatever's left standing is genuinely prime.

Visualize it this way: you're looking at a grid of numbers, and primes "shine through" while composites get blotted out in systematic waves. The result is a perfect map of primes up to N, generated without ever needing to test any individual number for divisibility.

Why It Matters

The Encryption That Protects Your Life Online

When you visit a banking website, your browser and the server perform a handshake that encrypts the connection. The most common method, RSA encryption, rests on a simple asymmetric fact: multiplying two large primes together is easy, but factoring the result back into its prime components is astronomically hard.

An RSA key might use two prime numbers, each roughly 1,024 bits long — numbers with around 300 decimal digits. Multiply them and you get a 2,048-bit number. A modern computer could generate these primes in milliseconds. But an attacker trying to factor their product? Even with all the computing power on Earth working in parallel, it would take longer than the age of the universe.

The sieve isn't used to generate these 300-digit primes directly — at that scale, specialized primality tests take over — but it's often the first step: generating a pool of smaller primes for candidate testing, building lookup tables, or running the segmented sieve (a modern variant) to sift through ranges efficiently.

The Density of Primes

Here's a remarkable fact: as numbers get larger, primes become sparser, but not arbitrarily so. The Prime Number Theorem, proven in 1896, gives a precise description of their density. The number of primes less than N is approximately N / ln(N).

That formula has a vivid consequence. Near 1,000, roughly 1 in every 7 numbers is prime — ln(1,000) ≈ 6.9. Near 1,000,000, it's about 1 in 14 — ln(1,000,000) ≈ 13.8. Near 1 billion, 1 in 21. Primes thin out logarithmically: doubling the scale of your numbers doesn't halve the density, it merely nudges it slightly lower.

The Sieve of Eratosthenes is essentially the physical instantiation of this thinning. Watch it run: the early steps (crossing out multiples of 2, then 3) eliminate huge swaths of numbers. But as you march further from the origin, each new prime eliminates a smaller fraction of remaining candidates. The survivors become rarer but never disappear entirely — there are infinitely many primes, a fact Euclid proved with breathtaking elegance around 300 BCE.

The Details

Who Was Eratosthenes?

Eratosthenes of Cyrene (c. 276–194 BCE) was one of antiquity's most astonishing polymaths. Born in what is now Libya, he was appointed chief librarian of the Library of Alexandria around 246 BCE — one of the most prestigious scholarly positions in the ancient world. He tutored the future Ptolemy IV Philopator, catalogued stars, and produced early maps of the known world, coining the term "geography" in the process.

His most famous achievement might be measuring the Earth's circumference — using nothing but shadows, geometry, and a few hundred miles of distance between two Egyptian cities. He observed that at noon on the summer solstice in Syene (modern Aswan), the sun was directly overhead — a stick cast no shadow. In Alexandria, at the same moment, the shadow angle was about 7.2 degrees, or roughly 1/50th of a full circle. Knowing the distance between the cities, he could compute the full circumference: approximately 250,000 stadia. Depending on which "stadion" unit he used, this was either remarkably close to or nearly exactly equal to Earth's modern-measured circumference of about 40,075 km.

A polymath who measured the planet also had time to think carefully about prime numbers.

The Attribution Puzzle

Here's a historical wrinkle worth knowing: Eratosthenes may not have invented the sieve himself. The earliest surviving text that describes the algorithm and attributes it to him is Introduction to Arithmetic by Nicomachus of Gerasa, written in the early 2nd century CE — roughly 400 years after Eratosthenes' death. Scholars have noted that Eratosthenes may have coined the name "sieve" (in Greek, koskinon) for an existing technique rather than inventing the method from scratch. His original writings on the subject don't survive.

What we can say with confidence: the intellectual tradition of Alexandria, and Eratosthenes in particular, is where this idea crystallized into the algorithm we still teach today.

The Algorithm's Efficiency

For a 2,200-year-old idea, the Sieve of Eratosthenes holds up remarkably well in computer science terms. Its time complexity is O(n log log n) — computer science notation meaning "the time to sieve up to n grows slightly faster than n, but only barely."

Here's the intuition: for each prime p, crossing out its multiples takes roughly n/p steps. Summing that across all primes up to n gives something proportional to n × (1/2 + 1/3 + 1/5 + 1/7 + ...) — a sum over all prime reciprocals. This sum grows as log log n, hence the complexity. It's strikingly efficient: to find all primes up to a million, modern implementations take milliseconds.

Modern Variants

The classical sieve has spawned a family of improvements:

The Segmented Sieve divides the range into small chunks (segments) that fit in CPU cache, dramatically improving real-world performance by avoiding cache misses. It can find all primes up to 10^12 while using only O(√n) memory — turning what was a memory-hungry algorithm into a lean, cache-friendly one.

The Sieve of Atkin (2003) has a slightly better asymptotic complexity, O(n / log log n), and is asymptotically faster than Eratosthenes for very large n. In practice, with careful optimization, it competes for the top spot in prime-generation benchmarks.

Wheel Factorization pre-skips multiples of small primes (2, 3, 5) before even starting the sieve, reducing the work by a third or more with almost no added complexity.

The Primes at the Frontier

In October 2024, a former Nvidia researcher named Luke Durant discovered the largest known prime number: 2^136,279,841 − 1, a Mersenne prime with 41,024,320 decimal digits. If you printed it out in standard text, it would fill roughly 80 pages. Durant spent approximately $2 million and a year of GPU computing time to find it through the Great Internet Mersenne Prime Search (GIMPS) — the 52nd Mersenne prime ever confirmed.

That's the frontier: after 2,300 years of searching, humans have confirmed only 52 primes of the Mersenne type. Each new discovery is a genuine mathematical event.

Near the record, the density of primes is impossibly thin. But the sieve's basic logic still applies: we know these gigantic primes exist because the theoretical framework — grounded in ideas Eratosthenes helped crystallize — tells us infinitely many of them await discovery.

What Primes Look Like in Practice

Run the sieve on paper for small numbers and a pattern emerges. Among the numbers 2–50, you'll find 15 primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. Notice they cluster a bit at first — several pairs appear close together like (11, 13) and (17, 19) and (29, 31). These are called twin primes, separated by just 2. Whether infinitely many twin primes exist is one of the great unsolved problems in mathematics.

There are also stretches of consecutive composite numbers that can grow arbitrarily long — called prime gaps. The largest currently known maximal gap starts at a prime exceeding 10^20. Primes can be sparse, then suddenly cluster, then sparse again — their distribution follows a statistical regularity described by the Prime Number Theorem but never locks into a perfect rhythm. They remain, after two millennia, fundamentally surprising.

Takeaways

• The Sieve of Eratosthenes is 2,200 years old and still foundational — it underpins prime generation algorithms used in modern cryptography and computational mathematics.
• The algorithm's elegance is its simplicity: eliminate multiples systematically, stop at the square root, and everything left is prime. No division tests needed.
• Primes thin out logarithmically as numbers grow larger, a fact encoded in the Prime Number Theorem — the sieve shows this thinning visually as you run it.
• RSA encryption, which protects most of the internet's financial and personal data, depends entirely on the computational hardness of factoring large primes — making the ability to generate primes efficiently a matter of global security infrastructure.
• The frontier keeps moving: the largest known prime has over 41 million digits, discovered in 2024 using GPU-powered distributed computing — ancient mathematics at the cutting edge of technology.

Want to explore further? The GIMPS project lets you contribute your computer's idle time to the search for the next record prime. The MacTutor History of Mathematics archive has an excellent biography of Eratosthenes if you want to go deeper into the man behind the sieve.