Sieves & Factorization

The previous lesson handed us a fast test for whether a single number is prime. Many problems instead need the primes en masse: every prime below $n$, or the factorization of each of many queries, and testing each number independently wastes the structure shared across them. A sieve turns the question inside out. Rather than interrogate one number at a time, it lets each prime announce its own multiples, so the composites are eliminated collectively. The result is a precomputed table over $\mathrm{1..}n$ that answers is $k$ prime? in $O(1)$ and, with one more field, factors any $x\le n$ in $O(\log x)$.

The sieve of Eratosthenes

The idea is older than computers and disarmingly simple. Write the integers $2,3,\dots ,n$. The smallest unmarked number, $2$, is prime; cross out all of its multiples $4,6,8,\dots$. The next still-unmarked number, $3$, is prime; cross out $6,9,12,\dots$. Repeat. Whenever we reach an unmarked number it has survived every smaller prime, so it has no smaller divisor, hence it is prime, and we strike its multiples in turn. When we are done, the unmarked numbers are exactly the primes.

In the grid below, $\mathrm{1..100}$ is laid out ten per row: composites are shaded out (grey), $1$ is left blank, and the $25$ survivors $2,3,5,7,11,\dots ,97$ — the primes — are highlighted.

Two optimizations make the sieve fast and are worth stating precisely.

Why it is $O(n\log \log n)$

The work is dominated by the inner loop, which for each prime $p\le n$ strikes $\lfloor n/p\rfloor$ multiples. Summing over primes,

The naive worry is that $\sum 1/p$ behaves like the harmonic series $\sum 1/k=\Theta (\log n)$, which would give $O(n\log n)$. But the sum runs over primes only, which are sparse, and a classical theorem of Mertens says the reciprocal sum of primes grows far more slowly:

Hence the total work is $n(\ln \ln n+O(1))=O(n\log \log n)$.¹ The $\log \log n$ factor is, for all practical $n$, a small constant (under $5$ for $n=10^9$), so the sieve is effectively linear. Space is $O(n)$ for the array (one bit per number if packed). Starting at $p^2$ rather than $2p$ does not change the asymptotics but roughly halves the constant.

The linear sieve and smallest prime factors

The Eratosthenes sieve strikes some composites more than once: $12$ is hit by $2$ (as $2\cdot 6$) and by $3$ (as $3\cdot 4$). The redundancy is exactly the $\log \log n$ factor. A linear sieve removes it by guaranteeing that every composite is crossed out exactly once, by its smallest prime factor (SPF). As a bonus it records that smallest prime factor, which is the key to fast factorization below.

Maintain a growing list of primes found so far. For each $i$ from $2$ to $n$, and for each known prime $p$ in increasing order, mark the product $i\cdot p$ as composite with smallest prime factor $p$. The subtle line is the termination: as soon as $p$ divides $i$, we break.

Each composite $m\le n$ is written once, when $i=m/\text{spf}(m)$ and $p=\text{spf}(m)$, so the total number of marking operations is exactly the number of composites: the running time is $\Theta (n)$, with $O(n)$ space.² The classic Count Primes problem is solved by either sieve; the linear sieve is the right tool whenever you also need per-number factor data downstream.

The payoff is the $\text{spf}$ table itself: every prime maps to itself, every composite to its smallest prime factor, each entry written exactly once. The composite $12$, for instance, is struck only when $i=6,p=2$, never again by the larger prime $3$.

Factorization

With a precomputed SPF table: $O(\log x)$

Given the $\text{spf}$ array from the linear sieve, any $x\le n$ factors by peeling off its smallest prime factor and dividing it out, repeatedly, until $1$ remains.

Each division by a prime $p\ge 2$ at least halves $x$, so the outer process runs at most ${\log }_{2}x$ times: factorization is $O(\log x)$ once the table is built. This is what makes problems like Distinct Prime Factors of Product of Array and Smallest Value After Replacing With Sum of Prime Factors tractable across many values: sieve once, then factor each query in logarithmic time.

Without preprocessing: trial division and beyond

When $x$ is a one-off, or larger than any sieve we can afford, fall back to trial division: try each candidate divisor $d=2,3,4,\dots$ up to $\sqrt{x}$, dividing it out whenever it divides. The $\sqrt{x}$ bound is the same observation as in the primality lesson: if $x=ab$ with $a\le b$ then $a\le \sqrt{x}$, so the smallest nontrivial factor appears by $\sqrt{x}$; any factor left after the loop is the final large prime.

This costs $O(\sqrt{x})$. For genuinely large $x$ (say $64$-bit and beyond), $\sqrt{x}$ is too slow, and one reaches for Pollard's rho, a randomized factoring algorithm that finds a nontrivial factor in expected $O(x^{1/4})$ time via cycle-detection on a pseudorandom map, paired with the Miller–Rabin primality test to know when a factor is itself prime and recursion can stop.³

The name comes from the shape of the orbit. Iterating $x\mapsto x^2+1\mathrm{mod}n$ from a seed eventually repeats, so the trajectory runs down a tail and then loops a cycle — drawn out, it looks like the Greek letter $\rho$. On $n=91=7\cdot 13$ the seed $2$ feeds a four-step cycle; because the cycle's residues modulo $7$ collide before they collide modulo $91$, a difference $x_i-x_j$ shares the factor $7$ with $n$, which $\gcd (x_i-x_j,n)$ then extracts.

Multiplicative functions from the factorization

Once $x={\prod }_i{p}_i^{e_i}$ is in hand, a family of useful quantities are read straight off the exponents. Each is multiplicative, meaning its value on a product of coprimes is the product of its values, which is why each factors as a product over the distinct primes.

Number of divisors $\tau (x)$. A divisor of $x$ chooses, independently for each prime $p_i$, an exponent between $0$ and $e_i$ — that is $e_i+1$ choices. Multiplying the independent counts,

For $360=2^3\cdot 3^2\cdot 5^1$ this is $(3+1)(2+1)(1+1)=24$ divisors. The product literally counts cells of a grid: the exponents of $2$ and $3$ index a $4\times 3$ block of divisors of $2^3\cdot 3^2$, and the choice of the factor $5^0$ or $5^1$ stacks a second identical block behind it, so $4\cdot 3\cdot 2=24$.

Four Divisors and Closest Divisors are direct applications: the former asks for numbers with $\tau (x)=4$, the latter searches divisor pairs near $\sqrt{x}$.

Sum of divisors $\sigma (x)$. The divisors of $x$ are obtained by expanding ${\prod }_i(1+p_i+p_i^2+\cdots +p_i^{e_i})$; each bracket is a geometric series, so

Euler's totient $\phi (x)$ counts the integers in $[1,x]$ coprime to $x$. By inclusion–exclusion over the distinct prime factors, removing the fraction $1/p_i$ that each prime kills, it collapses to a clean product:

For example $\phi (360)=360(1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})=96$.

When $\phi$ is needed for every number up to $n$, do not factor each one; sieve $\phi$ directly. Initialize $\phi [i]=i$, then for each prime $p$ sweep its multiples and apply the factor $(1-1/p)$ once, i.e. $\phi [m]-=\phi [m]/p$ for each multiple $m$ of $p$:

This runs in $O(n\log \log n)$, the same harmonic-over-primes sum as the plain sieve, and gives every totient at once.⁴

Takeaways

• The sieve of Eratosthenes marks composites by striking each prime's multiples from $p^2$ with stride $p$; survivors are prime. The cost is ${\sum }_{p\le n}n/p=O(n\log \log n)$ by Mertens' theorem, space $O(n)$.
• The linear sieve strikes each composite exactly once — by its smallest prime factor — running in $\Theta (n)$ while recording $\text{spf}[x]$; the break when $p\mid i$ is what enforces the once-only invariant.
• With an SPF table, any $x\le n$ factors in $O(\log x)$ by repeatedly dividing by $\text{spf}[x]$; without preprocessing, trial division to $\sqrt{x}$ costs $O(\sqrt{x})$, and Pollard's rho + Miller–Rabin handle large $x$.
• From $x=\prod p_i^{e_i}$ the multiplicative functions follow: $\tau (x)=\prod (e_i+1)$, $\sigma (x)=\prod \frac{p_i^{e_i+1}-1}{p_i-1}$, and Euler's totient $\phi (x)=x\prod (1-1/p_i)$.
• $\phi$ over an entire range is itself sieved in $O(n\log \log n)$; never factor each number when a sieve will compute them all together.