Sieve Techniques

“Sieving” means: for each candidate, touch all of its multiples. The total cost is the harmonic series, $O(N\log N)$ — or $O(N\log \log N)$ when restricted to primes.

The complexity facts

Loop	Cost
for each $i\le N$: for each multiple of $i$	$\sum N/i=O(N\log N)$
for each prime $p\le N$: for each multiple	${\sum }_{p}N/p=O(N\log \log N)$
for each prime $p$: starting at $p^2$	still $O(N\log \log N)$, smaller constant
linear sieve (each composite marked once)	$O(N)$

Prime sieve

vector<bool> comp(N + 1, false);
for (int i = 2; (long long)i * i <= N; i++)
    if (!comp[i])
        for (int j = i * i; j <= N; j += i) comp[j] = true;

Memory: vector<bool> is bit-packed, so $N=10^8$ costs 12 MB. Odd-only sieving halves it again.

Linear sieve — smallest prime factor

vector<int> spf(N + 1, 0), primes;
for (int i = 2; i <= N; i++) {
    if (!spf[i]) { spf[i] = i; primes.push_back(i); }
    for (int p : primes) {
        if (p > spf[i] || (long long)i * p > N) break;
        spf[i * p] = p;
    }
}

The p > spf[i] break is what guarantees each composite is marked exactly once — by its smallest prime factor. This gives $O(N)$ and an $O(\log n)$ factorisation for every $n\le N$.

Sieving multiplicative functions

Any multiplicative $f$ can be computed for all $n\le N$ in $O(N)$ alongside the linear sieve, by handling three cases:

if (!spf[i])            f[i] = fOfPrime(i);                    // i is prime
else if (i % p == 0)    f[i * p] = fOfPrimePower(...);         // p divides i: same prime
else                    f[i * p] = f[i] * f[p];                // coprime: multiplicative

Works for $\phi$, $\mu$, $d$, $\sigma$, and any function you can evaluate on prime powers.

Sieving over multiples — the general pattern

// for every i, accumulate something over its multiples
for (int i = 1; i <= N; i++)
    for (int j = i; j <= N; j += i)
        f[j] += g[i];

$O(N\log N)$, and it computes any Dirichlet-style transform. Uses:

Task	Body
Number of divisors	d[j]++
Sum of divisors	sig[j] += i
Möbius transform (subset-sum over divisors)	f[j] += g[i]
Count multiples of each $i$ in an array	cnt[i] += present[j]
$\gcd$-based counting	count how many array elements each $i$ divides

The gcd-counting idiom

// cntDiv[d] = how many array elements are divisible by d
for (int d = 1; d <= N; d++)
    for (int m = d; m <= N; m += d) cntDiv[d] += freq[m];
// then exactly[d] = pairs with gcd exactly d, by descending Möbius
for (int d = N; d >= 1; d--) {
    exact[d] = C(cntDiv[d], 2);
    for (int m = 2*d; m <= N; m += d) exact[d] -= exact[m];
}

This solves “count pairs/subsets with a given gcd” in $O(N\log N)$ — one of the most reused number-theory patterns in competitive programming.

Segmented sieve

Primes in $[L,R]$ with $R\le 10^{12}$ and $R-L\le 10^6$:

vector<bool> comp(R - L + 1, false);
for (long long p : primesUpToSqrtR) {
    long long start = max(p * p, (L + p - 1) / p * p);
    for (long long j = start; j <= R; j += p) comp[j - L] = true;
}
if (L == 1) comp[0] = true;                     // 1 is not prime

Memory $O(\sqrt{R}+(R-L))$ instead of $O(R)$.

Block sieving for cache

For $N\ge 10^8$, process the array in blocks of ~32 KB so each block fits in L1 cache. Typically a 2-3× speedup over a flat sieve, because the flat version thrashes memory.

Sieving in other domains

The idea generalises well beyond primes:

• Sieve of divisors — as above.
• Sieve over subsets — SOS DP is a sieve over the subset lattice, $O(2^{n}n)$.
• Sieve over a range of exponents — for problems about $p^k$.
• Sieving a DP — “for each state, push to all reachable states” is the same harmonic pattern when transitions are multiples.

The rule of thumb

Whenever you catch yourself writing “for each $n$, loop over its divisors”, flip it to “for each $d$, loop over its multiples”. Same answer, $O(N\log N)$ instead of $O(N\sqrt{N})$.

See also: Sieve of Eratosthenes · Divisor Functions · Möbius Function