Sieve of Eratosthenes

The Sieve of Eratosthenes finds all prime numbers up to a limit by repeatedly marking multiples of known primes.

It is a preprocessing algorithm for many prime-related queries.

Core Idea

Start by assuming numbers are prime. For each prime p, mark multiples of p as composite. It is enough to start marking at p * p because smaller multiples were already handled by smaller primes.

The sieve is much faster than testing each number independently by trial division.

Python Example

def sieve(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
 
    for p in range(2, int(limit ** 0.5) + 1):
        if is_prime[p]:
            for multiple in range(p * p, limit + 1, p):
                is_prime[multiple] = False
 
    return is_prime

is_prime[x] tells whether x is prime.

Common Confusions

The sieve finds many primes at once. If only one number needs to be tested, a different primality check may be simpler.

The limit controls memory use because the boolean array has limit + 1 entries.

When To Use It

Use the sieve when many queries ask whether numbers up to a known limit are prime, or when an algorithm needs a list of primes.