The Sieve Of Eratosthenes

Given an integer $N$, return a list of all prime numbers from 2 to $N$ (inclusive) using the Sieve of Eratosthenes algorithm. For example, $N = 30$ → [2, 3, 5, 7, 11, 13, 17, 19, 23, 29].

Instead of checking each number individually (which takes $O(\sqrt{N})$ per number), the Sieve marks all multiples of each prime as composite in bulk. Start from the smallest prime (2), mark all its multiples as not prime, then move to the next unmarked number, and repeat. The outer loop only runs up to $\sqrt{N}$ because any composite number's smallest prime factor must be $\leq \sqrt{N}$.

1. Create a boolean array is_prime of size $N+1$, initialized to True.
2. Set is_prime[0] = is_prime[1] = False.
3. For each $i$ from 2 to $\lfloor \sqrt{N} \rfloor$: if is_prime[i] is True, mark all multiples starting at $i^2$ as False.
4. Collect all indices where is_prime[i] is still True.

• Starting the inner loop from $2i$ instead of $i^2$ — the smaller multiples were already marked by earlier primes
• Not marking 0 and 1 as non-prime before collecting results
• Using a list of integers instead of a boolean array — wastes memory

The Sieve of Eratosthenes is the gold standard for generating all primes up to $N$. Understanding why the inner loop starts at $i^2$ (not $2i$) and why the outer loop only goes to $\sqrt{N}$ is key to grasping its efficiency.