The Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any limit you choose. It works by systematically crossing off multiples of each prime, starting with 2, until the only numbers left unmarked are primes. Invented over 2,200 years ago by the Greek mathematician Eratosthenes of Cyrene (276–194 BC), it remains one of the fastest known methods for generating a list of primes and is still used in modern computing and number theory.
How the Algorithm Works
Say you want to find every prime number up to 50. You start by writing out all the numbers from 2 to 50. (1 is not prime by definition, so it’s excluded.) At first, treat every number in the list as a potential prime. Then you begin the sifting process:
- Start with 2. It’s the smallest prime. Cross off every multiple of 2 (4, 6, 8, 10, and so on). Those are all composite numbers.
- Move to the next unmarked number, which is 3. Cross off every multiple of 3 that hasn’t already been crossed off (9, 15, 21, etc.).
- Move to the next unmarked number, which is 5. Cross off its remaining multiples (25, 35, etc.).
- Move to 7. Cross off its remaining multiples (49).
Once you’ve done this, every number still unmarked in your list is prime. For the range up to 50, you’d be left with: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, and 47.
Two Shortcuts That Speed Things Up
There’s a clever detail baked into the algorithm. When you start crossing off multiples of a prime p, you don’t need to begin at 2 × p. You can start at p × p. For example, when you get to 5, you skip 10 (already crossed off as a multiple of 2), 15 (already crossed off as a multiple of 3), and 20 (multiple of 2 again). The first multiple of 5 that hasn’t already been handled is 5 × 5 = 25. This saves a lot of redundant work.
The second shortcut is knowing when to stop. You only need to sieve up to the square root of your upper limit. If you’re finding primes up to 50, the square root of 50 is about 7.07, so you only need to sieve with the primes 2, 3, 5, and 7. The reason: any composite number larger than the square root must have at least one prime factor smaller than the square root. So by the time you’ve handled all primes up to 7, every composite number in the list has already been crossed off.
Why It’s So Fast
The sieve’s power comes from its simplicity. Each step is just marking entries in a list, which a computer can do almost instantly. The total work required to find all primes up to n grows at a rate of roughly n × log(log(n)), which is very close to linear. In practical terms, that means doubling your range barely more than doubles the computation time.
Compare that to the brute-force approach called trial division, where you check each number individually by trying to divide it by smaller primes. Trial division grows much faster, roughly proportional to n^(3/2) divided by (log n)². For small ranges the difference is negligible, but for larger ones the sieve pulls dramatically ahead. Research from Harvey Mudd College found that for generating more than about a million primes, the sieve clearly wins. And because the log(log(n)) factor grows incredibly slowly, the sieve is effectively faster for all practical sizes.
The tradeoff is memory. The basic sieve needs to hold an entry for every number up to your limit, so the memory requirement is proportional to n. For most modern computers, this isn’t an issue until n reaches into the billions. Segmented versions of the sieve break the range into chunks to work around memory limits when the range is truly enormous.
A Worked Example: Primes Up to 30
Write out the numbers 2 through 30. Start with 2 and cross off 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30. Move to 3, cross off 9, 15, 21, 27 (6, 12, 18, 24, and 30 were already gone). Move to 5, cross off 25 (everything else is already handled). The square root of 30 is about 5.5, so you’re done. The primes left standing: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. That’s all ten primes below 30, found with nothing more than counting and crossing off.
How It Compares to Other Sieves
The Sieve of Eratosthenes isn’t the only prime sieve, but it’s the most straightforward. The Sieve of Atkin, developed in 2003, uses a more complex approach based on quadratic equations and modular arithmetic to identify primes. In theory, Atkin’s sieve has a slight edge for very large ranges, but in practice, benchmarks tell a different story. A comparative study testing both algorithms on a range of one million numbers found Eratosthenes finished in about 1.85 seconds while Atkin took 3.39 seconds. The simpler method’s lower overhead makes it faster in real-world use for generating all primes up to a given limit.
Both sieves produce identical results, confirmed through independent primality testing. The Sieve of Sundaram is another alternative that works by eliminating certain arithmetic sequences, but it also tends to be slower in practice than Eratosthenes’ original approach.
Where It’s Used Today
Prime numbers are foundational to modern encryption. Secure communication on the internet relies on the difficulty of factoring large numbers into their prime components. Generating the prime numbers needed for these systems requires efficient algorithms, and the Sieve of Eratosthenes is a standard choice when you need to produce many primes up to a known limit.
It’s also a staple task in computer science education and programming interviews, because it demonstrates key concepts like algorithmic efficiency and the difference between brute-force and optimized approaches. The algorithm translates cleanly into code in virtually any programming language, typically in under 15 lines.
Where the classic sieve falls short is generating primes within a specific range (say, all primes between 10 million and 11 million) or running efficiently across multiple processor cores. These scenarios require modified versions of the algorithm. But for the straightforward task of listing every prime up to a ceiling, the method Eratosthenes devised in the third century BC remains remarkably hard to beat.