Sieve of Eratosthenes Algorithm Tutorial

Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm that finds all prime numbers up to $n$ by iteratively marking multiples of each prime as composite. It runs in $O(n \log \log n)$ time.

You start with $2$ (the first prime) and mark all its multiples. Then you move to the next unmarked number and repeat.

function sieve(n):
    isPrime = array of size n + 1, initialized to true
    isPrime[0] = false
    isPrime[1] = false

    for i from 2 to sqrt(n):
        if isPrime[i]:
            for j from i * i to n, step i:
                isPrime[j] = false

    return isPrime

Starting from $i^2$: When marking multiples of $i$, you start at $i^2$ because smaller multiples like $2i$, $3i$, etc. have already been marked by smaller primes.

Stopping at $\sqrt{n}$: Any composite number $\leq n$ has a factor $\leq \sqrt{n}$. You've already marked all composites by the time you reach $\sqrt{n}$.

Applications: You use the Sieve for prime factorization, cryptography key generation, number theory problems, and generating prime tables for competitive programming.

Time complexity: $O(n \log \log n)$ for the sieve.

Space complexity: $O(n)$ for the boolean array.