--- title: Sieves & Factorization module: Mathematical Algorithms moduleNumber: 10 lessonNumber: 3 order: 1003 summary: | The previous lesson tested one number for primality; here we ask for _all_ primes up to $n$ at once. The **sieve of Eratosthenes** cross-cuts composites in $O(n\log\log n)$, and a **linear sieve** does it in $O(n)$ while recording each number's **smallest prime factor**, which then factors any $x \le n$ in $O(\log x)$. From a factorization $x = \prod p_i^{e_i}$ the multiplicative functions $\tau$, $\sigma$, and Euler's totient $\varphi$ fall out immediately. topics: [Number Theory] sources: - book: CLRS ref: "Ch. 31 — Number-Theoretic Algorithms" - book: Skiena ref: "§ — Number Theory / Primes" - book: Erickson ref: "Ch. — (number theory)" practice: - title: 'Count Primes' slug: count-primes difficulty: Medium - title: 'Four Divisors' slug: four-divisors difficulty: Medium - title: 'Distinct Prime Factors of Product of Array' slug: distinct-prime-factors-of-product-of-array difficulty: Medium - title: 'Smallest Value After Replacing With Sum of Prime Factors' slug: smallest-value-after-replacing-with-sum-of-prime-factors difficulty: Medium - title: 'Closest Divisors' slug: closest-divisors difficulty: Medium --- 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** inverts the computation: rather than test one number at a time, it strikes out the multiples of each prime, eliminating the composites collectively. The result is a precomputed table over $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 ancient and 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, no smaller prime struck it, 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, $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. $$ % caption: The sieve over $1..100$: composites shaded out, $1$ blank, the 25 surviving % primes highlighted. \begin{tikzpicture}[ cell/.style={draw, minimum size=6.6mm, inner sep=0, font=\scriptsize}, x=7mm, y=7mm] \definecolor{acc}{HTML}{2348F2} % composite shading behind every cell, then blank 1, then prime highlight \foreach \n in {1,...,100}{ \pgfmathtruncatemacro{\col}{mod(\n-1,10)} \pgfmathtruncatemacro{\row}{div(\n-1,10)} \fill[black] (\col-0.47,-\row-0.47) rectangle (\col+0.47,-\row+0.47); } \fill[white] (-0.47,0.47) rectangle (0.47,-0.47); \foreach \n in {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}{ \pgfmathtruncatemacro{\col}{mod(\n-1,10)} \pgfmathtruncatemacro{\row}{div(\n-1,10)} \fill[acc!20] (\col-0.47,-\row-0.47) rectangle (\col+0.47,-\row+0.47); } \foreach \n in {1,...,100}{ \pgfmathtruncatemacro{\col}{mod(\n-1,10)} \pgfmathtruncatemacro{\row}{div(\n-1,10)} \node[cell] at (\col,-\row) {\n}; } \end{tikzpicture} $$ Two optimizations make the sieve fast and are worth stating precisely. > **Remark (Start at $p^2$).** When we process prime $p$, every multiple $kp$ with > $k < p$ has already been struck, as it was a multiple of the smaller prime > factor $k$ (or of a prime dividing $k$). So the first _new_ composite $p$ > contributes is $p \cdot p = p^2$. We may begin crossing out at $p^2$, and we > may stop processing primes once $p^2 > n$ entirely. > **Remark (Stride by $p$).** From $p^2$ the multiples are $p^2, p^2+p, p^2+2p, \dots$, so > the inner loop advances by `i += p`, never recomputing a product. ```algorithm caption: $\textsc{Sieve}(n)$ — mark composites, return the prime indicator array $P[0..n] \gets \text{true}$; $P[0] \gets \text{false}$; $P[1] \gets \text{false}$ for $c \gets 2$ to $\lfloor\sqrt{n}\rfloor$ do if $P[c]$ then // if candidate is prime $f \gets c^2$ // skip factors of smaller primes while $f \le n$ do $P[f] \gets \text{false}$ // sieve out the factor $f \gets f + c$ // stride by prime return $P$ ``` ::impl{algo="sieve_of_eratosthenes"} ### 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, $$ \sum_{p \le n} \frac{n}{p} = n \sum_{p \le n} \frac{1}{p}. $$ 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: > **Lemma (Mertens).** $\displaystyle\sum_{p \le n} \frac{1}{p} = \ln\ln n + > O(1)$. Hence the total work is $n(\ln\ln n + O(1)) = O(n\log\log n)$.[^clrs-sieve] 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$). That redundancy accounts for 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**. > **Invariant.** When we mark $i \cdot p$ with $p \mid i$ and then stop, $p$ is > the smallest prime factor of $i$. For any later prime $q > p$, the number > $i \cdot q$ has smallest prime factor $p$ (since $p \mid i \mid i\cdot q$), so > $i\cdot q$ will instead be struck when its true cofactor $i\cdot q / p$ reaches > it, _not_ here. Breaking is what prevents the double-strike. ```algorithm caption: $\textsc{LinearSieve}(n)$ — compute $\text{spf}[x]$ for every $x \le n$ $\text{spf}[0..n] \gets 0$; $\text{primes} \gets [\,]$ for $i \gets 2$ to $n$ do if $\text{spf}[i] = 0$ then // $i$ is prime $\text{spf}[i] \gets i$; append $i$ to $\text{primes}$ for each $p$ in $\text{primes}$ do if $p > \text{spf}[i]$ or $i \cdot p > n$ then break $\text{spf}[i \cdot p] \gets p$ return $\text{spf}, \text{primes}$ ``` ::impl{algo="linear_sieve"} 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 equals the number of composites: the running time is $\Theta(n)$, with $O(n)$ space.[^skiena-sieve] 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$. $$ % caption: Linear sieve: each composite carries its smallest prime factor $\text{spf}[x]$, % written once \begin{tikzpicture}[every node/.style={font=\small}, x=11mm, y=10mm] \definecolor{acc}{HTML}{2348F2} \foreach \x in {2,...,13}{ \node[draw, minimum size=8mm, inner sep=0] (n\x) at (\x,0.9) {$\x$}; } \node[font=\footnotesize] at (0.4,0.9) {$x$}; \node[font=\footnotesize] at (0.0,-0.2) {$\text{spf}[x]$}; \foreach \x/\s/\p in {2/2/1,3/3/1,4/2/0,5/5/1,6/2/0,7/7/1,8/2/0,9/3/0,10/2/0,11/11/1,12/2/0,13/13/1}{ \ifnum\p=1 \node[acc] at (\x,-0.2) {$\s$}; \else \node at (\x,-0.2) {$\s$}; \fi } \node[draw=acc, very thick, minimum size=8mm, inner sep=0] at (12,0.9) {}; \node[acc, font=\footnotesize] at (8,-1.2) {12 = 2 x 6 struck once, by p = 2 = spf[12]}; \end{tikzpicture} $$ ## 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. ```algorithm caption: $\textsc{Factor}(x)$ — full prime factorization of $x \le n$ via $\text{spf}$ $F \gets \{\}$ // map prime $\to$ exponent while $x > 1$ do $p \gets \text{spf}[x]$ while $x \bmod p = 0$ do $x \gets x / p$; $F[p] \gets F[p] + 1$ return $F$ ``` ::impl{algo="spf_factorization"} 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. $$ % caption: Divide by $\text{spf}[x]$ until $1$; the chain of factors collects in the % accent box \begin{tikzpicture}[ every node/.style={font=\small}, num/.style={draw, circle, minimum size=10mm, inner sep=1pt}, >=stealth, x=20mm, y=14mm] \definecolor{acc}{HTML}{2348F2} \useasboundingbox (-0.4,0.5) rectangle (6.4,-1.35); \node[num] (a) at (0,0) {$360$}; \node[num] (b) at (1,0) {$180$}; \node[num] (c) at (2,0) {$90$}; \node[num] (d) at (3,0) {$45$}; \node[num] (e) at (4,0) {$15$}; \node[num] (f) at (5,0) {$5$}; \node[num] (g) at (6,0) {$1$}; \draw[->] (a) -- node[above, text=acc]{/ 2} (b); \draw[->] (b) -- node[above, text=acc]{/ 2} (c); \draw[->] (c) -- node[above, text=acc]{/ 2} (d); \draw[->] (d) -- node[above, text=acc]{/ 3} (e); \draw[->] (e) -- node[above, text=acc]{/ 3} (f); \draw[->] (f) -- node[above, text=acc]{/ 5} (g); \node[draw=acc, very thick, fill=acc!15, inner xsep=6pt, inner ysep=6pt] at (3,-1.0) {$360 = 2^3\,3^2\,5$}; \end{tikzpicture} $$ ### 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](/algorithms/mathematical-algorithms/modular-exponentiation-and-primality): 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. ```algorithm caption: $\textsc{TrialFactor}(x)$ — factor a single $x$ in $O(\sqrt{x})$ $F \gets \{\}$; $d \gets 2$ while $d \cdot d \le x$ do while $x \bmod d = 0$ do $x \gets x / d$; $F[d] \gets F[d] + 1$ $d \gets d + 1$ if $x > 1$ then $F[x] \gets F[x] + 1$ // leftover prime $> \sqrt{x}$ return $F$ ``` ::impl{algo="trial_division"} 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.[^clrs-pollard] The name comes from the shape of the orbit. Iterating $x \mapsto x^2 + 1 \bmod 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. $$ % caption: Pollard's rho on $n=91$ with $f(x)=x^2+1$: the orbit of $2$ forms a tail into a % cycle — the $\rho$ shape \begin{tikzpicture}[every node/.style={font=\small}, >=stealth, x=1cm, y=1cm] \definecolor{acc}{HTML}{2348F2} \node[draw, circle, minimum size=9mm, inner sep=0] (t) at (-3.7,0) {$2$}; \node[draw, circle, minimum size=9mm, inner sep=0, draw=acc, fill=acc!15, very thick] (c0) at (0,1.5) {$5$}; \node[draw, circle, minimum size=9mm, inner sep=0, draw=acc, fill=acc!15, very thick] (c1) at (2.0,0) {$26$}; \node[draw, circle, minimum size=9mm, inner sep=0, draw=acc, fill=acc!15, very thick] (c2) at (0,-1.5) {$40$}; \node[draw, circle, minimum size=9mm, inner sep=0, draw=acc, fill=acc!15, very thick] (c3) at (-2.0,0) {$54$}; \draw[->] (t) to[bend left=10] (c3); \draw[->, acc] (c0) -- (c1); \draw[->, acc] (c1) -- (c2); \draw[->, acc] (c2) -- (c3); \draw[->, acc] (c3) -- (c0); \node[font=\footnotesize] at (-3.7,-0.95) {tail}; \node[acc, font=\footnotesize] at (3.6,-1.7) {gcd(x\textsubscript{i} - x\textsubscript{j}, 91) = 7}; \end{tikzpicture} $$ ::impl{algo="pollard_rho"} **Worked example (rho splits $91$).** Iterate $f(x) = x^2 + 1 \bmod 91$ from $x_0 = 2$, running a slow pointer $x$ (one step) against a fast pointer $y$ (two steps) — Floyd's tortoise-and-hare cycle detector — and testing $\gcd(\lvert x - y\rvert, 91)$ at each round. After one round the slow pointer is at $f(2) = 5$ and the fast pointer at $f(f(2)) = f(5) = 26$, so we test $\gcd(\lvert 5 - 26\rvert, 91) = \gcd(21, 91) = 7$, a nontrivial factor, so $91 = 7 \cdot 13$. The reason it works: modulo the hidden factor $7$, the sequence $2, 5, 26{\equiv}5, \dots$ collides after only a few steps (there are just $7$ residues), while modulo $91$ it has not yet repeated — so $x \equiv y \pmod 7$ but $x \not\equiv y \pmod{91}$, the gap that makes $\gcd(x-y, 91)$ land on $7$. The expected number of steps to a collision modulo a factor $p$ is $O(\sqrt p)$ by the birthday bound, giving the $O(n^{1/4})$ expected running time. ## 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, $$ \tau(x) = \prod_i (e_i + 1). $$ For $360 = 2^3\cdot3^2\cdot5^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\cdot3^2$, and the choice of the factor $5^0$ or $5^1$ stacks a second identical block behind it, so $4\cdot3\cdot2 = 24$. $$ % caption: $\tau(360)=(3{+}1)(2{+}1)(1{+}1)$ counts cells of an exponent grid: a % $4\times 3$ block of $2^a3^b$, doubled by the factor $5^0$ or $5^1$. \begin{tikzpicture}[every node/.style={font=\small}, x=12mm, y=12mm] \definecolor{acc}{HTML}{2348F2} \useasboundingbox (-1.6,1.6) rectangle (5.3,-3.6); % back block: a SECOND identical 4x3 grid offset behind (the "x5" / 5^1 layer that % doubles 12 into 24); faint cells so the front numbers stay readable \foreach \a/\b in {0/0,1/0,2/0,3/0, 0/1,1/1,2/1,3/1, 0/2,1/2,2/2,3/2}{ \node[draw=black, minimum size=9mm, inner sep=0] at (\a+0.36,-\b+0.32) {}; } \node[font=\scriptsize] at (3.95,0.62) {x 5}; % front block (x1): the 12 divisors of 2^3 3^2 \foreach \a/\b/\v in {0/0/1,1/0/2,2/0/4,3/0/8, 0/1/3,1/1/6,2/1/12,3/1/24, 0/2/9,1/2/18,2/2/36,3/2/72}{ \node[draw, fill=acc!12, minimum size=9mm, inner sep=0, font=\scriptsize] at (\a,-\b) {$\v$}; } % axis labels \node[font=\footnotesize] at (1.5,1.1) {exponent of 2: 0 to 3}; \node[font=\footnotesize, rotate=90] at (-1.0,-1) {exponent of 3: 0 to 2}; \node[font=\footnotesize] at (1.7,-3.25) {4 x 3 x 2 = 24 divisors}; \end{tikzpicture} $$ `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 + \dots + p_i^{e_i})$; each bracket is a geometric series, so $$ \sigma(x) = \prod_i \frac{p_i^{\,e_i+1} - 1}{p_i - 1}. $$ [**Euler's totient**](/algorithms/mathematical-algorithms/combinatorics) $\varphi(x)$ counts the integers in $[1, x]$ coprime to $x$. By inclusion–exclusion over the distinct prime factors, removing the fraction $1/p_i$ of integers each prime divides, it reduces to a product: $$ \varphi(x) = x \prod_i \parens{1 - \frac{1}{p_i}}. $$ For example $\varphi(360) = 360\,(1-\tfrac12)(1-\tfrac13)(1-\tfrac15) = 96$. ::impl{algo="multiplicative_functions"} When $\varphi$ is needed for _every_ number up to $n$, do not factor each one; sieve $\varphi$ directly. Initialize $\varphi[i] = i$, then for each prime $p$ sweep its multiples and apply the factor $(1 - 1/p)$ once, i.e. $\varphi[m] \mathrel{-}= \varphi[m]/p$ for each multiple $m$ of $p$: ```algorithm caption: $\textsc{TotientSieve}(n)$ — compute $\varphi(x)$ for all $x \le n$ for $i \gets 0$ to $n$ do $\varphi[i] \gets i$ for $p \gets 2$ to $n$ do if $\varphi[p] = p$ then // $p$ is prime $m \gets p$ while $m \le n$ do $\varphi[m] \gets \varphi[m] - \varphi[m] / p$ // apply $(1-1/p)$ $m \gets m + p$ return $\varphi$ ``` ::impl{algo="totient_sieve"} This runs in $O(n\log\log n)$, the same harmonic-over-primes sum as the plain sieve, and gives every totient at once.[^erickson-nt] ## Segmented sieving and counting the primes Two extensions matter at scale: sieving beyond available memory, and counting primes without enumerating them. **Segmented sieving.** The plain sieve needs an array of size $n$, which fails when $n$ is, say, $10^{12}$ — no machine holds a trillion-bit array. The **segmented sieve** fixes this: compute the primes up to $\sqrt n$ once (a small sieve), then process $[2, n]$ in cache-sized windows $[\ell, \ell + \Delta)$, marking each window with the multiples of every prime $\le \sqrt n$. Memory drops to $O(\sqrt n + \Delta)$ while the total work stays $O(n\log\log n)$, and because each window fits in cache the constant factor improves. This is how record prime enumerations (all primes below $10^{18}$) are actually run. To count primes in a range $[\ell, r]$ — the shape of _Closest Prime Numbers in Range_ — sieve just that window against the small primes below $\sqrt r$. $$ % caption: Segmented sieve: small primes up to $\sqrt n$ (left) mark each cache-sized % window of $[2,n]$ in turn, so only $O(\sqrt n + \Delta)$ memory is live. \begin{tikzpicture}[every node/.style={font=\small}, x=1cm, y=1cm] \definecolor{acc}{HTML}{2348F2} \useasboundingbox (-0.6,1.1) rectangle (10.2,-1.7); \node[draw=acc, fill=acc!12, very thick, minimum width=20mm, minimum height=9mm, align=center] (base) at (1,0) {primes\\ to sqrt(n)}; \foreach \i/\lab in {0/{[2 : W)},1/{[W : 2W)},2/{[2W : 3W)}}{ \node[draw, minimum width=17mm, minimum height=9mm, font=\footnotesize] (w\i) at (4.0+\i*2.0,0) {\lab}; \draw[->, acc] (base.east) to[bend left=10] (w\i.north); } \node[font=\small] at (9.4,0) {...}; \node[acc, font=\footnotesize] at (4.7,-1.2) {each window sieved by the same small primes, then discarded}; \end{tikzpicture} $$ **How many primes are there?** The sieve enumerates primes; the **prime number theorem** counts them: $\pi(n) \sim n/\ln n$, so a random integer near $n$ is prime with probability about $1/\ln n$.[^pnt] This is what tells RSA key generation how many random candidates it must test before finding a 1024-bit prime (about $\ln 2^{1024} \approx 710$ on average). Counting $\pi(n)$ _without_ listing every prime — the Meissel–Lehmer method and its modern refinement by **Lagarias, Miller, and Odlyzko** — computes $\pi(n)$ in roughly $O(n^{2/3})$ time and far less space, reaching values of $n$ well beyond what any sieve could enumerate.[^lmo] **The linear sieve's lineage.** The once-per-composite linear sieve is usually credited to Paul Pritchard's sublinear "wheel" sieves and to Gries and Misra (1978), who gave the SPF-recording form used here.[^gries-misra] Its main value is the **smallest-prime-factor table** it produces, not the marginal speedup over Eratosthenes: the table turns every subsequent factorization query into an $O(\log x)$ table walk. ## 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** $\varphi(x) = x\prod(1-1/p_i)$. - $\varphi$ 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. [^clrs-sieve]: **CLRS**, Ch. 31 — Number-Theoretic Algorithms: divisibility, primes, and the cost of generating them; the $O(n\log\log n)$ sieve bound follows from $\sum_{p\le n}1/p = \ln\ln n + O(1)$. [^skiena-sieve]: **Skiena**, § — Number Theory / Primes: the sieve of Eratosthenes and its linear refinement that records smallest prime factors for $O(\log x)$ factorization. [^clrs-pollard]: **CLRS**, Ch. 31 — Number-Theoretic Algorithms (§31.9): Pollard's rho heuristic for factoring large integers, with Miller–Rabin (§31.8) as the companion primality test. [^erickson-nt]: **Erickson**, Ch. — (number theory): multiplicative functions $\tau$, $\sigma$, $\varphi$ read off the prime factorization, and sieving $\varphi$ over a range. [^pnt]: The prime number theorem, $\pi(n)\sim n/\ln n$ (Hadamard and de la Vallée Poussin, 1896). See **Skiena**, § — Number Theory / Primes, for the algorithmic consequence for random-prime generation. [^gries-misra]: D. Gries and J. Misra, "A linear sieve algorithm for finding prime numbers," _Communications of the ACM_ **21**(12), 1978; P. Pritchard, "A sublinear additive sieve for finding prime numbers," _CACM_ **24**(1), 1981. [^lmo]: J. C. Lagarias, V. S. Miller, A. M. Odlyzko, "Computing $\pi(x)$: the Meissel–Lehmer method," _Mathematics of Computation_ **44**(170), 1985.