The Sieve of Eratosthenes

Pillar: Shape — "The harmonic sum \(N/2 + N/3 + N/5 + \ldots\) traces the area under the \(1/x\) curve — that's what gives \(O(N \log \log N)\)." Pillar: Chain — "Each composite is marked by its smallest prime factor — a chain of eliminations."

The Problem

You need all primes up to \(N\), where \(N\) can be as large as \(10^7\).

The naive approach: for each number from \(2\) to \(N\), check if it's prime by trial division up to \(\sqrt{k}\). That's \(O(\sqrt{k})\) per number, \(O(N\sqrt{N})\) total. For \(N = 10^7\), that's roughly \(3 \times 10^{10}\) operations. Too slow.

You need something fundamentally different. Instead of testing each number one by one, what if you could mark all the composites in one pass?

The Sieve Idea

Flip the perspective. Don't ask "is this number prime?" Ask: "which numbers does this prime eliminate?"

Start with every number from \(2\) to \(N\) marked as potentially prime. Then:

Take \(2\), the smallest prime. Mark all multiples of \(2\): \(4, 6, 8, 10, 12, \ldots\) These are all composite.
Take \(3\), the next unmarked number (so it's prime). Mark all multiples of \(3\): \(9, 12, 15, 18, \ldots\) (some already marked, that's fine).
Take \(5\), the next unmarked number. Mark \(25, 30, 35, \ldots\)
Continue until you've processed all primes up to \(\sqrt{N}\).

Every number that survives without being marked is prime.

Why Start Marking at \(p^2\)

When you reach prime \(p\), you might think the inner loop should start at \(2p\). But consider: every composite number \(k < p^2\) that's a multiple of \(p\) can be written as \(p \times m\) where \(m < p\). That means \(m\) has a prime factor smaller than \(p\), so \(k\) was already marked when you processed that smaller prime.

For \(p = 5\): the multiples \(10 = 5 \times 2\), \(15 = 5 \times 3\), \(20 = 5 \times 4\) were already marked by \(2\) or \(3\). The first "new" multiple is \(25 = 5 \times 5 = p^2\).

Starting at \(p^2\) instead of \(2p\) doesn't change correctness — just avoids redundant work.

Trace: Sieve for \(N = 30\)

Start with all numbers \(2\) through \(30\) unmarked. We only need to process primes up to \(\sqrt{30} \approx 5\).

\(p = 2\): Mark \(4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30\).

2	3	~~4~~	5	~~6~~	7	~~8~~	9	~~10~~	11	~~12~~	13	~~14~~	15	~~16~~	17	~~18~~	19	~~20~~	21	~~22~~	23	~~24~~	25	~~26~~	27	~~28~~	29	~~30~~

\(p = 3\): Start at \(9\). Mark \(9, 15, 21, 27\) (others like \(12, 18, 24, 30\) already marked).

2	3	~~4~~	5	~~6~~	7	~~8~~	~~9~~	~~10~~	11	~~12~~	13	~~14~~	~~15~~	~~16~~	17	~~18~~	19	~~20~~	~~21~~	~~22~~	23	~~24~~	25	~~26~~	~~27~~	~~28~~	29	~~30~~

\(p = 5\): Start at \(25\). Mark \(25\) (\(30\) already marked).

2	3	~~4~~	5	~~6~~	7	~~8~~	~~9~~	~~10~~	11	~~12~~	13	~~14~~	~~15~~	~~16~~	17	~~18~~	19	~~20~~	~~21~~	~~22~~	23	~~24~~	~~25~~	~~26~~	~~27~~	~~28~~	29	~~30~~

Surviving primes: \(2, 3, 5, 7, 11, 13, 17, 19, 23, 29\).

That's 10 primes up to 30. Three passes through the inner loop and you're done.

Complexity — The Shape Argument

This is the centerpiece of the lesson. The sieve's time complexity is \(O(N \log \log N)\), and the reason involves one of the sharpest connections in number theory.

Counting the Total Work

For each prime \(p\), the inner loop marks roughly \(N/p\) multiples. The total number of marking operations across all primes is:

\[\frac{N}{2} + \frac{N}{3} + \frac{N}{5} + \frac{N}{7} + \frac{N}{11} + \ldots = N \sum_{p \leq N} \frac{1}{p}\]

So everything hinges on this one sum: the sum of reciprocals of all primes up to \(N\).

The Sum of Prime Reciprocals

Mertens' theorem (1874) tells us:

\[\sum_{p \leq N} \frac{1}{p} = \Theta(\log \log N)\]

That double logarithm is not a typo. It grows absurdly slowly. For \(N = 10^7\), \(\log \log N \approx 2.9\). For \(N = 10^{18}\), \(\log \log N \approx 3.6\). The sieve is very nearly linear.

The Visual Intuition

Think about the harmonic series first. The sum of reciprocals of ALL integers up to \(N\) is:

\[\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{N} = \Theta(\log N)\]

You can see this by plotting \(f(x) = 1/x\) and noticing the sum approximates the area under the curve from \(1\) to \(N\), which is \(\int_1^N \frac{1}{x}\,dx = \ln N\).

Now the sieve doesn't sum over ALL integers — only over primes. How much sparser are primes compared to all integers? The Prime Number Theorem says: among integers near \(k\), roughly \(1/\ln k\) of them are prime. So the density of primes decays logarithmically.

When you restrict the harmonic sum to only prime positions, you're summing \(1/p\) where the gaps between terms grow like \(\ln p\). This thins out the sum from \(\log N\) to \(\log(\log N)\). Intuitively, you're taking the "logarithm" of the harmonic series by skipping to only the prime terms, and the logarithm of \(\log N\) is \(\log \log N\).

Another way to see it: group the primes by magnitude. Primes near \(k\) contribute about \(\frac{1}{k}\) each, and there are about \(\frac{dk}{\ln k}\) of them in a small interval. So the total contribution from primes near \(k\) is \(\frac{dk}{k \ln k}\). Integrating:

\[\int_2^N \frac{dk}{k \ln k} = \ln(\ln N) - \ln(\ln 2) = \Theta(\log \log N)\]

That substitution \(u = \ln k\), \(du = dk/k\) turns \(\int \frac{dk}{k \ln k}\) into \(\int \frac{du}{u} = \ln u = \ln \ln k\). The double log emerges from the primes being just sparse enough to compress one layer of logarithm.

The Bottom Line

Total sieve work: \(N \times \Theta(\log \log N) = O(N \log \log N)\) time, \(O(N)\) space. For \(N = 10^7\), this is roughly \(3 \times 10^7\) — essentially linear.

Smallest Prime Factor (SPF) Sieve

The standard sieve tells you which numbers are prime. But what if you need to factorize many numbers, not just identify primes?

The idea: for each number \(i\), store its smallest prime factor (SPF). Then factorizing any \(n \leq N\) becomes trivial — keep dividing by \(\text{SPF}[n]\) until you reach \(1\).

Building the SPF Table

When you encounter a prime \(p\) during the sieve, iterate over its multiples. For each multiple \(m\), set \(\text{SPF}[m] = p\) only if \(\text{SPF}[m]\) hasn't been set yet. Since you process primes in increasing order, the first prime to reach \(m\) is always the smallest one.

Key difference from the standard sieve: the SPF sieve starts the inner loop at \(p\) (not \(p^2\)), because you need to tag EVERY multiple with its smallest prime factor, not just the unmarked ones.

Trace: Factorize \(360\) Using the SPF Table

First, you need the SPF table built up to at least \(360\). Here are the relevant entries:

Number	SPF
\(360\)	\(2\)
\(180\)	\(2\)
\(90\)	\(2\)
\(45\)	\(3\)
\(15\)	\(3\)
\(5\)	\(5\)

Now factorize \(360\):

Step	Current Value	SPF[current]	Action
1	\(360\)	\(2\)	Divide by \(2\): \(360 / 2 = 180\)
2	\(180\)	\(2\)	Divide by \(2\): \(180 / 2 = 90\)
3	\(90\)	\(2\)	Divide by \(2\): \(90 / 2 = 45\)
4	\(45\)	\(3\)	Divide by \(3\): \(45 / 3 = 15\)
5	\(15\)	\(3\)	Divide by \(3\): \(15 / 3 = 5\)
6	\(5\)	\(5\)	Divide by \(5\): \(5 / 5 = 1\)

Result: \(360 = 2^3 \times 3^2 \times 5^1\). Six steps — one per prime factor counted with multiplicity. That's \(O(\log n)\), since any number \(n\) has at most \(\log_2 n\) prime factors (the smallest prime is \(2\), so the most factors you can pack is \(\log_2 n\)).

Compare this to trial division: \(O(\sqrt{n})\) per query. For \(n = 10^7\), that's \(\sim 3162\) operations per factorization. With SPF, it's at most \(23\) operations. If you need to factorize thousands of numbers, the SPF sieve pays for itself immediately.

The Code

Standard Sieve

vector<bool> sieveOfEratosthenes(int limit) {
    vector<bool> isPrime(limit + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int candidate = 2; (long long)candidate * candidate <= limit; candidate++) {
        if (isPrime[candidate]) {
            for (int multiple = candidate * candidate; multiple <= limit; multiple += candidate) {
                isPrime[multiple] = false;
            }
        }
    }
    return isPrime;
}

Note the cast (long long)candidate * candidate. Without it, when candidate exceeds \(46340\), the product \(46341^2 = 2{,}147{,}488{,}281 > 2^{31} - 1\) overflows a 32-bit int.

Smallest Prime Factor Sieve

vector<int> buildSmallestPrimeFactor(int limit) {
    vector<int> smallestPrimeFactor(limit + 1, 0);
    for (int candidate = 2; candidate <= limit; candidate++) {
        if (smallestPrimeFactor[candidate] == 0) {
            for (int multiple = candidate; multiple <= limit; multiple += candidate) {
                if (smallestPrimeFactor[multiple] == 0) {
                    smallestPrimeFactor[multiple] = candidate;
                }
            }
        }
    }
    return smallestPrimeFactor;
}

When smallestPrimeFactor[candidate] == 0, no smaller prime divided candidate, so it's prime. The inner loop starts at candidate (not candidate * candidate) because every multiple needs its SPF recorded.

Factorization Using SPF

map<int, int> factorizeWithSPF(int number, vector<int>& smallestPrimeFactor) {
    map<int, int> primeExponents;
    while (number > 1) {
        int primeFactor = smallestPrimeFactor[number];
        while (number % primeFactor == 0) {
            primeExponents[primeFactor]++;
            number /= primeFactor;
        }
    }
    return primeExponents;
}

Each iteration extracts all copies of the current smallest prime factor, then moves to the next. The inner while groups consecutive divisions by the same prime, so you don't look up smallestPrimeFactor more than necessary.

Complexity

Standard sieve: \(O(N \log \log N)\) time, \(O(N)\) space.
SPF sieve: \(O(N \log \log N)\) time, \(O(N)\) space.
Factorization via SPF: \(O(\log n)\) per query.

When to Use Which

Standard sieve: You just need the list of primes (or a primality lookup table). Uses vector<bool> which is memory-efficient (bit-packed).
SPF sieve: You need to factorize many numbers up to \(N\). The \(O(N)\) precomputation pays for itself when you have multiple factorization queries. Uses vector<int> — more memory than vector<bool>, but you get \(O(\log n)\) factorization.

You'll see the SPF sieve again in L4 (Multiplicative Functions and the Mobius Sieve), where it becomes the backbone for computing divisor counts, divisor sums, and Euler's totient across all numbers simultaneously.

Common Mistakes

Sieve array off by one. If \(N = 10^7\), you need vector<bool> isPrime(N + 1, true) — size \(N + 1\), not \(N\). Indexing goes from \(0\) to \(N\) inclusive.
Forgetting \(0\) and \(1\). Neither is prime. Set isPrime[0] = isPrime[1] = false before the sieve loop. Miss this and every query for "number of primes up to \(N\)" is off by two.
Integer overflow in \(p^2\). When \(p > 46340\), the product p * p exceeds \(2^{31} - 1\). Cast to long long before the comparison: (long long)candidate * candidate <= limit. This is easy to forget because the sieve "works" for small inputs without the cast — the bug only surfaces for large \(N\).

Quick Recap

The sieve marks composites by iterating over multiples of each prime, instead of testing each number individually. This flips \(O(N\sqrt{N})\) trial division into \(O(N \log \log N)\).
Start marking at \(p^2\), not \(2p\) — all smaller multiples were already hit by smaller primes.
The \(\log \log N\) factor comes from the sum of prime reciprocals (Mertens' theorem), which is the harmonic series restricted to prime positions — one logarithm thinner than the full harmonic series.
The SPF sieve stores each number's smallest prime factor, enabling \(O(\log n)\) factorization per query after \(O(N \log \log N)\) precomputation.
Watch for off-by-one in array size, uninitialized \(0\) and \(1\), and integer overflow in \(p^2\).

Problems

Problem	Link	Difficulty	Focus
LC 204 — Count Primes	leetcode.com/problems/count-primes	Easy	Direct sieve application
LC 2761 — Prime Pairs with Target Sum	leetcode.com/problems/prime-pairs-with-target-sum	Medium	Sieve + two-pointer on prime list
CSES — Counting Divisors	cses.fi/problemset/task/1713	Medium	Multiple queries — SPF sieve for fast factorization