Back to Number Theory Dsa

Linear Sieve Invariants

September 22, 2026 Wasil Zafar 9 min read

Derive why each composite is processed exactly once.

Table of Contents

  1. Intuition, Vocabulary and Foundations
  2. Step-by-Step Derivations and Algorithms
  3. Implementation, Complexity and Engineering
  4. Applications, Case Studies and Exercises

Intuition, Vocabulary and Foundations

A sieve precomputes arithmetic information for every integer in a prefix. The classical Sieve of Eratosthenes marks a composite once for each relevant prime divisor. Euler’s linear sieve assigns each composite through one canonical event instead: multiply a smaller integer by the composite’s smallest prime factor.

Let $\operatorname{spf}(n)$ denote the smallest prime factor of $n\gt1$. Every composite $n$ has the unique decomposition $n=ip$, where $p=\operatorname{spf}(n)$ and $p\le\operatorname{spf}(i)$. For example, $60=30\cdot2$. Although $60$ is also $20\cdot3$ and $12\cdot5$, only $30\cdot2$ uses the smallest prime as multiplier under the sieve rule. This resembles assigning each package one permanent processing station.

The SPF table exposes prime-power structure. If $i=rp^e$ with $p\nmid r$, multiplying by $p$ extends an existing prime power, whereas multiplying by a smaller new prime introduces a coprime factor. That distinction drives recurrences for Euler’s totient $\varphi$, the Möbius function $\mu$, the divisor count $\tau$, and the divisor sum $\sigma$.

When processing $i$, iterate through primes $p\le\operatorname{spf}(i)$ and assign $ip$; stop immediately after $p=\operatorname{spf}(i)$. Every composite is generated exactly once, by the pair $(n/\operatorname{spf}(n),\operatorname{spf}(n))$.

ConceptDefinition or invariantConcrete exampleNon-example or boundaryQuestion answered
Smallest prime factor$\operatorname{spf}(n)=\min\{p:p\mid n,\ p\text{ prime}\}$$\operatorname{spf}(45)=3$$\operatorname{spf}(1)$ is undefined by conventionWhich prime controls the recurrence?
Prime detectionWhen $i\ge2$ and $\operatorname{spf}(i)=0$, $i$ is primeAt $i=7$, append $7$A zero entry before its turn is not globally meaningfulWhen is a new prime discovered?
Canonical composite pair$n=ip$ with $p=\operatorname{spf}(n)$$42=21\cdot2$$42=14\cdot3$ uses the wrong multiplierWhich loop iteration owns $n$?
Existing-prime case$p=\operatorname{spf}(i)$$i=12,p=2$ creates $24$Treating $p$ as coprime to $i$Does an exponent increase?
New-prime case$p\lt\operatorname{spf}(i)$, hence $\gcd(p,i)=1$$i=25,p=2$ creates $50$Using multiplicativity when $p\mid i$May values multiply directly?
Totient recurrence$\varphi(ip)=p\varphi(i)$ if $p\mid i$, otherwise $(p-1)\varphi(i)$$\varphi(24)=2\varphi(12)=8$Applying the coprime formula in both casesHow is $\varphi$ propagated?
Möbius recurrence$\mu(ip)=0$ if $p\mid i$, otherwise $-\mu(i)$$\mu(30)=-\mu(15)=-1$A square factor cannot have nonzero $\mu$Is a prime repeated?
Multiplicative function$f(ab)=f(a)f(b)$ when $\gcd(a,b)=1$$\tau(12\cdot5)=\tau(12)\tau(5)$Multiplicative does not mean completely multiplicativeWhich recurrences require coprimality?

Step-by-Step Derivations and Algorithms

Initialize $\varphi(1)=1$, $\mu(1)=1$, $\tau(1)=1$, and $\sigma(1)=1$. Process $i=2,3,\ldots,n$ in increasing order. If spf[i] is zero, no earlier prime generated $i$, so $i$ is prime. Set its SPF to itself and initialize its arithmetic values from prime-power formulas.

For each stored prime $p$, stop if $ip\gt n$; otherwise set $\operatorname{spf}(ip)=p$. If $p=\operatorname{spf}(i)$, then $p\mid i$, and $\varphi(ip)=p\varphi(i)$ while $\mu(ip)=0$. If $p\lt\operatorname{spf}(i)$, then $p\nmid i$, and multiplicativity gives $\varphi(ip)=(p-1)\varphi(i)$ and $\mu(ip)=-\mu(i)$.

After processing the equal-prime case, break. Continuing would generate numbers whose true smallest prime factor is smaller than the new multiplier, duplicating work owned by another outer-loop index.

For divisor functions, track the exponent $e$ and power $p^e$ of the smallest prime in $i$. When that exponent increases, replace the factor $e+1$ in $\tau(i)$ with $e+2$. For $i=rp^e$, retain $\sigma(r)$ and use $\sigma(rp^{e+1})=\sigma(rp^e)+\sigma(r)p^{e+1}$. When a new coprime prime is introduced, multiply $\tau(i)$ by $2$ and $\sigma(i)$ by $1+p$.

Linear Sieve Invariants algorithm map
flowchart TD
    A["Process next i"] --> B{"spf[i] is zero?"}
    B -->|Yes| C["Record i as prime"]
    B -->|No| D["Use existing state"]
    C --> E["Iterate primes p"]
    D --> E
    E --> F{"i times p exceeds limit?"}
    F -->|Yes| G["Advance outer loop"]
    F -->|No| H["Assign spf[i times p] = p"]
    H --> I{"p equals spf[i]?"}
    I -->|Yes| J["Extend prime power and break"]
    I -->|No| K["Apply coprime recurrence"]
    K --> E
    J --> G

At the start of iteration $i$, every smaller integer has final arithmetic values, and each generated product $ip$ receives $p$ as its true smallest prime factor. The break makes the ownership pair unique, so only $O(n)$ successful composite transitions occur; total time is $O(n)$ and the arrays plus prime list use $O(n)$ memory.

Implementation, Complexity and Engineering

The implementation computes smallest prime factors, $\varphi$, $\mu$, $\tau$, and $\sigma$ in one pass. It also records how many times each composite is assigned, turning the uniqueness claim into an executable invariant.

Arrays indexed through limit are simple and fast, but memory depends on representation. Five fixed-width 64-bit value arrays require roughly $40(n+1)$ bytes before other state. Packed arrays are preferable to boxed language objects for large limits.

from math import gcd, isqrt


def linear_sieve(limit):
    if limit < 1:
        raise ValueError("limit must be at least 1")

    primes = []
    spf = [0] * (limit + 1)
    phi = [0] * (limit + 1)
    mu = [0] * (limit + 1)
    tau = [0] * (limit + 1)
    sigma = [0] * (limit + 1)
    exponent = [0] * (limit + 1)
    prime_power = [1] * (limit + 1)
    sigma_core = [1] * (limit + 1)
    assignments = [0] * (limit + 1)

    phi[1] = mu[1] = tau[1] = sigma[1] = 1

    for i in range(2, limit + 1):
        if spf[i] == 0:
            spf[i] = i
            primes.append(i)
            phi[i] = i - 1
            mu[i] = -1
            exponent[i] = 1
            prime_power[i] = i
            sigma_core[i] = 1
            tau[i] = 2
            sigma[i] = i + 1

        for prime in primes:
            composite = i * prime
            if composite > limit:
                break
            spf[composite] = prime
            assignments[composite] += 1

            if prime == spf[i]:
                phi[composite] = phi[i] * prime
                mu[composite] = 0
                exponent[composite] = exponent[i] + 1
                prime_power[composite] = prime_power[i] * prime
                sigma_core[composite] = sigma_core[i]
                tau[composite] = (
                    tau[i] // (exponent[i] + 1)
                    * (exponent[composite] + 1)
                )
                sigma[composite] = (
                    sigma[i] + sigma_core[i] * prime_power[composite]
                )
                break

            phi[composite] = phi[i] * (prime - 1)
            mu[composite] = -mu[i]
            exponent[composite] = 1
            prime_power[composite] = prime
            sigma_core[composite] = sigma[i]
            tau[composite] = tau[i] * 2
            sigma[composite] = sigma[i] * (prime + 1)

    return {
        "primes": primes, "spf": spf, "phi": phi, "mu": mu,
        "tau": tau, "sigma": sigma, "assignments": assignments,
    }


def factor_with_spf(value, spf):
    if value < 1 or value >= len(spf):
        raise ValueError("value is outside the sieve range")
    factors = []
    while value > 1:
        prime = spf[value]
        power = 0
        while value % prime == 0:
            value //= prime
            power += 1
        factors.append((prime, power))
    return factors


def direct_arithmetic_values(value):
    phi = sum(gcd(k, value) == 1 for k in range(1, value + 1))
    divisors = [d for d in range(1, value + 1) if value % d == 0]
    factor_count = 0
    remaining = value
    repeated = False
    candidate = 2
    while candidate * candidate <= remaining:
        if remaining % candidate == 0:
            power = 0
            while remaining % candidate == 0:
                remaining //= candidate
                power += 1
            factor_count += 1
            repeated |= power > 1
        candidate += 1
    if remaining > 1:
        factor_count += 1
    mu = 0 if repeated else (-1 if factor_count % 2 else 1)
    return phi, mu, len(divisors), sum(divisors)


data = linear_sieve(200)
assert data["primes"][:8] == [2, 3, 5, 7, 11, 13, 17, 19]
assert data["spf"][45] == 3
assert factor_with_spf(180, data["spf"]) == [(2, 2), (3, 2), (5, 1)]
assert data["phi"][36] == 12
assert data["mu"][30] == -1
assert data["mu"][12] == 0
assert data["tau"][60] == 12
assert data["sigma"][60] == 168

for value in range(1, 201):
    expected = direct_arithmetic_values(value)
    actual = tuple(data[name][value] for name in ("phi", "mu", "tau", "sigma"))
    assert actual == expected

for composite in range(4, 201):
    if data["spf"][composite] != composite:
        assert data["assignments"][composite] == 1

try:
    linear_sieve(0)
    raise AssertionError("invalid limit was accepted")
except ValueError:
    pass

print("all tests passed")
Engineering choiceTimeApproximate storageFailure modeMitigation
SPF-only linear sieve$O(n)$One integer array plus primesAssuming it is automatically smallestMeasure actual bytes and workload
SPF, $\varphi$, and $\mu$$O(n)$Three value arrays plus primesWrong repeated-prime recurrenceSeparate equal-SPF and coprime branches
Adding $\tau$ and $\sigma$$O(n)$Exponent, prime-power, and core arraysLosing the coprime remainder contributionTrack least-prime power and core explicitly
Boxed Python integers$O(n)$ operationsFar more than word size per elementMemory exhaustionUse packed arrays or a systems language
Fixed-width arithmetic$O(n)$Predictable bytes$\sigma(n)$ or prime powers overflowUse proven bounds and checked arithmetic
Assignment counters$O(n)$One diagnostic arrayShipping test-only memoryEnable only in verification builds
Eratosthenes alternative$O(n\log\log n)$Often compact and cache-friendlyRejecting it because it is not linearPrefer it when only primality is needed
Prefix differential testsOracle-dependentSmall test prefixTesting only primesCompare every value with definitions

Applications, Case Studies and Exercises

The linear sieve is most valuable when one pass must populate several multiplicative-function tables. Its proof is reusable: identify the least prime factor, distinguish whether its exponent grows, and express the new value from already finalized state.

Practice

Apply Linear Sieve Invariants

Case study 1 — trace the prefix through 20. For each outer value $i$, list the primes visited, composites assigned, and the iteration that triggers the break. Pay special attention to $12$: it is assigned from $i=6,p=2$, not from $i=4,p=3$. Checkpoint: every composite from $4$ through $20$ has exactly one owner pair. Success means the owner’s prime equals its smallest prime factor.

Case study 2 — build a reusable arithmetic table. Precompute spf, $\varphi$, $\mu$, $\tau$, and $\sigma$ through $10^6$. Record construction time, allocated bytes, and query throughput. Compare selected values with factorization formulas and every value through $5000$ with a direct oracle. Success means zero mismatches, no overflow, and documented memory per entry.

Hands-on extension — add the radical. Define $\operatorname{rad}(n)=\prod_{p\mid n}p$. When $p=\operatorname{spf}(i)$, use $\operatorname{rad}(ip)=\operatorname{rad}(i)$; otherwise use $\operatorname{rad}(ip)=p\operatorname{rad}(i)$. Implement the recurrence and verify every value through $1000$ using SPF factorization. Success means complete prefix agreement without postprocessing inside the sieve loop.

Tiered exercises. Recall: state the unique owner pair. Derive: prove its multiplier is the smallest prime factor. Implement: add the number of distinct prime factors. Debug: remove the equal-SPF break and count duplicates. Extend: design an interface for function-specific state and branch recurrences in one verified sieve engine.

Use the linear sieve when a bounded prefix needs SPF data or several multiplicative functions at once; use Eratosthenes when compact primality marking is simpler or faster in practice. The non-negotiable invariant is that the inner loop stops after the current smallest prime, so each composite is owned exactly once and every recurrence consumes finalized state.