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.

Function Contract

sieve(limit) expects a non-negative integer limit.

It returns a boolean list where is_prime[x] tells whether x is prime for 0 <= x <= limit. Values outside that range are not represented.

Python Example

def sieve(limit):
    if limit < 2:
        return [False] * (limit + 1)
 
    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.

Step-by-Step Example

For limit 10, start with 2 as prime and mark multiples 4, 6, 8, and 10 as composite. Then 3 is prime and marks 9. Numbers 5 and 7 remain prime.

The primes up to 10 are:

2, 3, 5, 7

Why Start at p * p

For a prime p, smaller multiples such as 2p, 3p, and so on have already been marked by smaller factors. The first new multiple that needs marking is p * p.

Complexity

The sieve runs in about O(n log log n) time and uses O(n) space for the boolean table.

Query Pattern

The sieve is strongest when preprocessing is reused. After building is_prime, each primality query up to the limit is just an array lookup:

if is_prime[x]:
    print("prime")

That makes sense when many queries share the same upper bound.

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.

Another common mistake is marking 0 and 1 as prime. They are not prime.

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.

Do not use a large sieve if the limit is enormous and only a few numbers need testing.

The Main Point

The sieve is preprocessing for many prime queries up to a known limit. Its strength is reuse after one marking pass.