Math Tools Math Tools
Share:
← Back to Blog

The Sieve of Eratosthenes: One of the Oldest Algorithms Still in Use

The Sieve of Eratosthenes: One of the Oldest Algorithms Still in Use

By Math Tools ·

The Sieve of Eratosthenes: One of the Oldest Algorithms Still in Use

More than 2,200 years ago, a Greek scholar in Alexandria described a way to find every prime number up to any limit. It needs no division, no multiplication tables beyond counting, and no cleverness about any individual number.

Today, versions of that same method are still among the fastest ways to generate large lists of primes on modern computers. Very few algorithms have lasted two millennia. The Sieve of Eratosthenes has, because its central idea is exactly right.

It Never Tests Whether a Number Is Prime

The obvious way to find primes is to take each number and test it: does anything divide it? The sieve does the opposite. It never examines a number to decide if it's prime.

Instead, it crosses out multiples. Whatever survives is prime by elimination. Working with multiples (which only need addition) instead of divisors (which need division) is what makes it so fast.

Who Was Eratosthenes?

Eratosthenes of Cyrene (c. 276–194 BC) was the chief librarian of the Library of Alexandria. He's famous for estimating Earth's circumference by comparing the angle of the Sun's rays in two cities, and his result was remarkably close to the true value.

His prime sieve doesn't survive in his own writings. It's described by Nicomachus of Gerasa in his Introduction to Arithmetic, written around 100 AD, who credits Eratosthenes.

How the Sieve Works

Let's find all primes up to 50.

Step 1: Write the numbers from 2 to 50.

Step 2: Circle 2, the first number. Cross out every multiple of 2 after it: 4, 6, 8, 10, …, 50.

Step 3: Move to the next number not crossed out: 3. Circle it. Cross out its multiples: 9, 15, 21, 27, 33, 39, 45 (6, 12, 18, … are already gone).

Step 4: Next survivor: 5. Circle it. Cross out 25, 35 (the rest are already crossed out).

Step 5: Next survivor: 7. Cross out 49.

Step 6: The next survivor is 11. But 11² = 121 is greater than 50, so stop. Every number still standing is prime:

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

That's all 15 primes up to 50. Compare with the list of prime numbers.

Two Clever Shortcuts

Start Crossing Out at p²

When you reach prime p, every multiple smaller than p², such as 2p, 3p, …, (p − 1)p, has a smaller factor and was already crossed out. So you can start at p². For 7, the first new number to cross out is 49.

Stop at √n

Once p² exceeds your limit n, there's nothing left to cross out. Any composite number up to n must have a factor no larger than √n, and those factors have already done their work. For n = 50, √50 ≈ 7.07, so the last sieving prime is 7. See square roots on the square roots list.

The Sieve in Code

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False
        p += 1
    return [i for i, prime in enumerate(is_prime) if prime]

This short function finds all 78,498 primes below one million in a fraction of a second.

How Fast Is It?

Crossing out multiples of p takes about n/p steps. Adding that over all primes up to √n gives:

n × (1/2 + 1/3 + 1/5 + 1/7 + …) ≈ n × ln(ln n)

So the sieve runs in O(n log log n) time. The log log n factor grows absurdly slowly: for n = 10⁹, ln(ln n) is only about 3.03. In practice the sieve is almost linear. Explore how slowly logarithms grow with the logarithm calculator.

An Insider Reference: Sieves at Modern Scale

The basic sieve has one weakness: it needs a true/false flag for every number up to n. For n = 10¹², that's far too much memory.

The fix is the segmented sieve. First sieve up to √n, then process the range in chunks small enough to fit in the CPU's fast cache memory, using only the small primes for each chunk. Open-source libraries such as primesieve, developed by Kim Walisch, combine segmentation with "wheel" tricks that skip multiples of 2, 3, 5 and 7 automatically. They can generate all primes below 10¹⁰ in well under a second on ordinary hardware.

Mathematicians have also designed new sieves. In 2003, A. O. L. Atkin and Daniel J. Bernstein published the Sieve of Atkin, which uses quadratic forms and has a slightly better theoretical running time. Yet carefully optimized Eratosthenes-style sieves remain very hard to beat in practice.

Two Concepts Worth Knowing

Composite Numbers

A composite number has a factor other than 1 and itself. The sieve works by identifying composites through their smallest prime factors. See the composite numbers list.

Time Complexity

Time complexity describes how an algorithm's running time grows with input size. The sieve's O(n log log n) makes it far faster for producing all primes up to n than testing each number separately with trial division.

Quick Answer: How Does the Sieve of Eratosthenes Work?

List the numbers from 2 to n. Starting with 2, keep the first uncrossed number as prime and cross out all its multiples from its square onward. Repeat with the next uncrossed number until its square exceeds n. The numbers left uncrossed are exactly the primes up to n.

Try Them Yourself

Print the counting table from 1 to 100 and sieve it by hand. You should end with 25 primes, and you'll only need to sieve with 2, 3, 5 and 7.

Next → Real life uses of LCM and GCF