Sieve of Eratosthenes

The Sieve of Eratosthenes is the classic way to find every prime up to some limit. Instead of testing each number for primality on its own, it does the opposite: it assumes everyone is prime, then crosses out the multiples of each prime it finds.

The slow way first

The obvious idea: for each number k, try dividing it by every smaller number to see if anything divides evenly. Testing one number is up to O(√k) work, and doing it for all n numbers is roughly O(n√n) — slow once n gets large.

The question to ask: am I redoing work? When I prove 2 is prime, I immediately know 4, 6, 8, … are not — they all have 2 as a factor. The sieve captures exactly that: discovering a prime lets you eliminate a whole family of composites at once.

The idea: cross out, don't test

Keep a boolean array is_prime where every entry starts True. Walk p from 2 upward. When you reach a p that is still True, it is prime — nothing below it crossed it out. Then mark all of its multiples p*p, p*p+p, … as False. When the sweep ends, the numbers still marked True are exactly the primes.

Two details make it fast. First, start crossing out at p*p, not 2*p: any smaller multiple of p (like 2*p or 3*p) already got crossed out by a smaller prime. Second, once p*p exceeds n, every remaining survivor is automatically prime — there is nothing left to mark.

Walk through it

Step through the animation. The pointer p sweeps left to right across the grid 2…30. Each time p lands on a cell still marked prime, that cell is highlighted and added to primes. Then its multiples are dimmed as composite. Watch 2 knock out the evens, 3 knock out the rest of its multiples, and 5 finish the job — after that every survivor (7, 11, 13, …) is prime with no more crossing out to do.

Pseudocode

is_prime = array of True for 0..n
is_prime[0] = is_prime[1] = False        # 0 and 1 are not prime
for p from 2 to n:
    if is_prime[p]:                      # p was never crossed out -> prime
        for m from p*p to n step p:      # start at p*p; smaller multiples already gone
            is_prime[m] = False          # m has factor p -> composite
primes = every i where is_prime[i] is still True
return primes

The Python solution

def count_primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, n + 1):
        if is_prime[p]:
            # p is prime; cross out its multiples
            for m in range(p * p, n + 1, p):
                is_prime[m] = False
    primes = [i for i in range(n + 1) if is_prime[i]]
    return primes

• is_prime is a boolean array; index i answers "is i still prime?" We size it n + 1 so index n exists.
• We set is_prime[0] and is_prime[1] to False up front — neither is prime by definition.
• The outer loop sweeps p from 2 to n. If is_prime[p] is still True, nothing crossed it out, so p is prime.
• The inner loop starts at p*p and steps by p, flipping each multiple to False. Starting at p*p skips multiples a smaller prime already handled.
• After the sweep, the comprehension collects every index that survived — those are all the primes up to n.

Complexity

The crossing-out work sums to n/2 + n/3 + n/5 + … over the primes, which is O(n log log n) — close to linear. We pay O(n) space for the boolean array, a worthwhile trade for the big speed win.

When this pattern shows up

Practice