vault

Linear Sieve

28 min read

Linear Sieve

The linear sieve (also called Euler’s sieve in cp-algorithms tradition, or the Gries-Misra sieve after the 1978 Communications of the ACM paper that first presented it cleanly) computes every prime up to a bound N in time Θ(N) — strictly linear, with no log-factor — by ensuring that every composite number is crossed off exactly once, by its smallest prime factor (SPF). The classical Sieve of Eratosthenes runs in Θ(N log log N) because each composite c with prime factorization p_1^{a_1} · ... · p_k^{a_k} is crossed off k times, once by each distinct prime divisor; the log log N is the average of k over composites up to N. The linear sieve removes this redundancy by tracking, for every integer, its smallest prime factor, and arranging the inner loop so that the crossing-off of c = i · p happens only when p is the smallest prime factor of c. The clever break condition if i % p == 0: break enforces this by terminating the inner loop the moment the p we are about to use would not be the smallest prime factor of the resulting composite. The pleasant side benefits — a populated smallest_prime_factor table — turn the same data structure into an O(log n) factorization oracle, an O(N) Euler totient φ(n) precompute, and an O(N) Möbius function μ(n) precompute, all by extending the inner loop by a few lines. For most competitive-programming and number-theoretic interview problems with N ≤ 10^7, the linear sieve is the expected answer.

1. Intuition — Each Composite Marked Once, By Its Smallest Prime Factor

The classical Sieve of Eratosthenes iterates p = 2, 3, 5, 7, 11, ... and, for each prime p, marks 2p, 3p, 4p, ... as composite. The redundancy is visible: 30 = 2·3·5 is marked by p = 2 (as 15·2), by p = 3 (as 10·3), and by p = 5 (as 6·5) — three times. Asymptotically, by Mertens’ theorem Σ_{p ≤ N} 1/p ~ log log N, so the total work is Θ(N log log N).

If we could mark each composite exactly once, the total work would drop to Θ(N). The linear sieve does this by deciding, in advance, which of c’s several “marker primes” we will use: the smallest one. Concretely, for each composite c = SPF(c) · m, we want exactly the iteration where the algorithm processes (i, p) = (m, SPF(c)) to mark c, and no other.

The trick to enforcing “exactly once by SPF” is the inner-loop break condition. The outer loop runs i = 2, 3, 4, ..., N. For each i, we iterate over primes p ≤ SPF(i) (the primes already discovered, in increasing order) and mark i · p as composite. Two facts make this correct:

  • Why p ≤ SPF(i)? If p > SPF(i), then i · p has factorization ... · SPF(i) · ... · p, and p is not the smallest prime factor — SPF(i) is smaller. So marking i · p here would violate the “by-SPF” rule; some earlier (smaller-i) iteration will mark it correctly when the time comes.
  • Why break (not just skip) when p == SPF(i)? Once p = SPF(i), the next prime p' in our loop would be larger than SPF(i), putting us in the forbidden regime above. So we break out.

A real-world analogy: imagine a class of students lined up in some canonical order, each asked to “tag” every multiple of their student-ID-number. To avoid duplicate tags (multiple students tagging 30 = 2·3·5), the rule becomes: “you tag a multiple m·k only if your ID k is the smallest prime factor of m·k.” The break condition is the rule that lets each student stop early, the moment they realize the next product they’d compute is somebody else’s responsibility.

The structural insight: every composite c ≥ 2 has a unique smallest prime factor, so there is exactly one (i, p) pair i = c / SPF(c), p = SPF(c) that “owns” c. The linear sieve enumerates these pairs once and only once.

2. Tiny Worked Example — Sieving Up to N = 20

Trace the linear sieve up to N = 20. We maintain two structures:

  • primes: a list of primes discovered so far.
  • spf: an array where spf[i] = 0 if not yet assigned; otherwise the smallest prime factor of i. (For i prime, spf[i] = i.)

Initialize primes = [], spf = [0] × (N + 1).

For i = 2:

  • spf[2] == 0 → 2 is prime. Append: primes = [2], spf[2] = 2.
  • Inner loop over primes: p = 2. Mark i · p = 4: spf[4] = 2. Check i % p = 2 % 2 = 0 → break.

For i = 3:

  • spf[3] == 0 → 3 is prime. primes = [2, 3], spf[3] = 3.
  • Inner loop: p = 2. 3 · 2 = 6, spf[6] = 2. 3 % 2 = 1 ≠ 0 → continue. p = 3. 3 · 3 = 9, spf[9] = 3. 3 % 3 = 0 → break.

For i = 4:

  • spf[4] == 2 ≠ 0 → 4 is composite (already marked by i = 2).
  • Inner loop: p = 2. 4 · 2 = 8, spf[8] = 2. 4 % 2 = 0 → break.

For i = 5:

  • spf[5] == 0 → 5 is prime. primes = [2, 3, 5], spf[5] = 5.
  • Inner loop: p = 2. 5 · 2 = 10, spf[10] = 2. 5 % 2 = 1 ≠ 0 → continue. p = 3. 5 · 3 = 15, spf[15] = 3. 5 % 3 = 2 ≠ 0 → continue. p = 5. 5 · 5 = 25 > 20 (out of range; if we still wanted, spf[25] = 5); break (5 % 5 = 0).

For i = 6:

  • spf[6] == 2 ≠ 0 → composite.
  • Inner loop: p = 2. 6 · 2 = 12, spf[12] = 2. 6 % 2 = 0 → break. (We do not try p = 3 even though 6 · 3 = 18 would be marked by some pair — we leave that to i = 9, p = 2, where 9 · 2 = 18 and spf[18] = 2.)

For i = 7:

  • spf[7] == 0 → 7 is prime. primes = [2, 3, 5, 7], spf[7] = 7.
  • Inner loop: p = 2. 7 · 2 = 14, spf[14] = 2. 7 % 2 = 1 ≠ 0. p = 3. 7 · 3 = 21 > 20; we typically still record spf[21] if we are sieving past N — but for this trace, we stop at the loop bound.

(Continuing — the pattern is now clear; let’s record the SPF table at the end.)

For i = 8: composite (SPF 2). Inner: p = 2, 8 · 2 = 16, spf[16] = 2, break.

For i = 9: composite (SPF 3). Inner: p = 2, 9 · 2 = 18, spf[18] = 2, 9 % 2 = 1. p = 3, 9 · 3 = 27 > 20. We do mark spf[18] = 2 here — and notice this is where 18 gets marked for the first and only time. Break.

For i = 10: composite (SPF 2). Inner: p = 2, 10 · 2 = 20, spf[20] = 2, break.

For i = 11..20: all primes greater than N/2, so the inner loop’s first product i · 2 exceeds N and we break immediately. They contribute themselves to primes and spf[i] = i.

Final spf table for i = 2..20:

i:   2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
spf: 2  3  2  5  2  7  2  3  2 11  2 13  2  3  2 17  2 19  2

Primes: [2, 3, 5, 7, 11, 13, 17, 19]. Each composite c was assigned spf[c] exactly once — by the (i, p) pair where i = c / SPF(c) and p = SPF(c). For c = 18: i = 9, p = 2; c = 20: i = 10, p = 2; c = 15: i = 5, p = 3. Trace each composite to confirm.

3. Why Each Composite Is Marked Exactly Once — Proof

This is the heart of the algorithm and worth a careful walk-through.

Theorem. The linear sieve marks every composite c ∈ [2, N] exactly once, via the iteration i = c / SPF(c), p = SPF(c).

Proof.

Existence. Let c ∈ [2, N] be composite, with SPF q = SPF(c). Set i = c / q. Since c is composite, i ≥ 2. We need to show that during the outer-loop iteration of value i, the inner loop reaches p = q and computes i · p = c before breaking.

The inner loop iterates over primes in increasing order: 2, 3, 5, ..., until either i · p > N (out of range) or i % p == 0 (break). The break condition i % p == 0 is equivalent to p | i, which means p ≤ SPF(i). So the inner loop continues as long as the current prime p < SPF(i), and stops just after processing p = SPF(i).

Now, q = SPF(c) = SPF(i · q). By the definition of SPF: every prime divisor of i is at least q (because q is the smallest prime divisor of i · q, so any prime divisor of i is at least q). In particular, SPF(i) ≥ q — meaning the inner loop reaches p = q (since the loop runs through all primes ≤ SPF(i), in increasing order). When it reaches p = q, we mark i · q = c. This proves existence.

Uniqueness. Suppose for contradiction c is marked by some other pair (i', p') with (i', p') ≠ (i, q) and i' · p' = c. Then p' is a prime divisor of c and i' = c / p'. By construction of the linear sieve, the inner loop only iterates over primes ≤ SPF(i'), and breaks immediately after SPF(i'). So p' ≤ SPF(i').

Two cases:

  1. p' = q (the SPF). Then i' = c / q = i, so (i', p') = (i, q) — contradiction.
  2. p' > q. Then p' > q = SPF(c) ≥ SPF(c / p') · ? — let’s reason: since q | c, and p' | c with p' > q, we have c = q · ... · p' · ..., so c / p' still contains q as a factor, i.e., q | (c / p') = i'. Hence SPF(i') ≤ q < p'. But the loop requires p' ≤ SPF(i'), so p' ≤ q, contradicting p' > q.

So no other pair can mark c. Uniqueness is proven. ∎

The break condition if i % p == 0: break is what enforces case (2)‘s contradiction. Without it, the inner loop would continue past p = SPF(i) and start processing primes that are not the smallest factor of i · p, double-marking composites.

4. Pseudocode

LinearSieve(N):
    spf := array of size N + 1, all zero
    primes := empty list
    for i := 2 to N:
        if spf[i] == 0:
            spf[i] := i                # i is prime
            append i to primes
        for each p in primes (in increasing order):
            if i * p > N:
                break                  # out of range
            spf[i * p] := p            # mark composite i*p with its SPF
            if i mod p == 0:
                break                  # p is SPF of i; further primes would not be SPF of i*p
    return spf, primes

The two break conditions handle different concerns: the first is the bound check; the second is the SPF correctness check.

A note on the two forms of the SPF break. This note uses if i mod p == 0: break. The canonical cp-algorithms implementation instead writes if pr[j] == lp[i]: break — i.e. “break when the current prime equals the smallest-prime-factor of i” (cp-algorithms). The two are equivalent given the loop’s invariant. The inner loop visits primes p in increasing order; i mod p == 0 first becomes true exactly when p reaches the smallest prime dividing i, which is SPF(i) (and, once spf[i] is populated, equals lp[i]). So i mod p == 0 and p == SPF(i) trigger on the same iteration. The i mod p == 0 form needs no separate spf[i]/lp[i] lookup and reads more directly as “stop once p divides i”; the p == lp[i] form makes the SPF-ownership argument textually obvious. Either is correct — do not combine them or change the inner-loop direction (see §9.2).

5. Python Implementation

def linear_sieve(n: int) -> tuple[list[int], list[int]]:
    """Return (smallest_prime_factor_array, primes_list) for [0, n].
 
    spf[i] for i >= 2: the smallest prime factor of i (so spf[p] = p iff p is prime).
    spf[0] = spf[1] = 0 (sentinel).
    primes: list of primes <= n, in increasing order.
    """
    spf = [0] * (n + 1)
    primes: list[int] = []
    for i in range(2, n + 1):
        if spf[i] == 0:
            spf[i] = i
            primes.append(i)
        for p in primes:
            if i * p > n:
                break
            spf[i * p] = p
            if i % p == 0:
                break
    return spf, primes
 
 
# Sanity check on N = 20 (matches §2)
spf, primes = linear_sieve(20)
assert primes == [2, 3, 5, 7, 11, 13, 17, 19]
assert spf[1:21] == [0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2]

The Python implementation is slower than the Sieve of Eratosthenes in absolute wall-clock time for N ≤ 10^7 because of CPython’s interpreter overhead per inner-loop iteration; the SoE’s tight arr[p*p::p] = [False] * len(...) slice assignment uses C-level bulk memory writes and dominates. The linear sieve’s advantage materializes either (a) in compiled C/C++/Rust, where each iteration is a few cycles, or (b) when you also need the spf table for downstream factorization (where the SoE’s False-flag table is insufficient).

6. Complexity

Time: Θ(N).

By the uniqueness proof in §3, the inner loop’s body executes once per composite in [2, N]. The outer loop runs N - 1 times, with O(1) work per iteration outside the inner loop. The total number of inner-loop iterations equals (composites in [2, N]) + (one extra “break” iteration per outer i) ≤ N + N = 2N. Each iteration is O(1) (one array write and one mod-check). Total: Θ(N).

Compare to the Sieve of Eratosthenes at Θ(N log log N). The ratio at N = 10^7 is log log 10^7 ≈ log(16) ≈ 2.8 — so the linear sieve does about 2.8× less work in operation count. In practice, the SoE wins on raw wall-clock for unmarked-array sieving because of memory-access pattern advantages (sequential writes to a single flag array, vs the linear sieve’s random-write to spf indexed by i * p). The break-even is implementation-dependent.

Space: Θ(N) for spf (one machine word per index in the simplest formulation; one byte per index if you only need primality; ~4 bytes per index for fitting spf values up to N). The primes list adds another Θ(N / log N) entries by the prime-counting theorem π(N) ~ N / log N.

For N = 10^7, spf at 4 bytes/entry is ~40 MB — fits in RAM but not in cache. The cache-locality penalty is the main reason linear sieves can lose to SoE in practice.

7. Applications — The SPF Table Earns Its Keep

The spf array, populated as a side effect of the sieve, doubles as a constant-time SPF oracle that turns several number-theoretic computations from “naïve” complexities into much better ones.

7.1 Factorization in O(log N)

Given n ≤ N, factorize by repeatedly dividing by spf[n]:

def factorize(n: int, spf: list[int]) -> list[tuple[int, int]]:
    """Return prime factorization of n as [(p_1, e_1), (p_2, e_2), ...]."""
    factors: list[tuple[int, int]] = []
    while n > 1:
        p = spf[n]
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        factors.append((p, e))
    return factors

Each iteration of the outer while n > 1 divides n by at least 2, so the loop runs at most log_2 N times. Total: O(log N) per query, after the O(N) preprocessing.

Without the SPF table, factorizing n requires trial division up to √n, costing O(√n / log n). For n = 10^9, that’s ~30000 ops vs ~30 with the SPF table — three orders of magnitude.

7.2 Euler’s Totient φ(n) for All n ≤ N

Euler’s totient φ(n) is the count of integers in [1, n] coprime to n. Multiplicative formula: if n = p_1^{a_1} · ... · p_k^{a_k}, then φ(n) = n · Π_i (1 - 1/p_i).

The linear sieve computes φ for all n in O(N) total by extending the inner loop. The recurrences (with i the outer index, p the inner prime):

  • If i is prime: φ[i] = i - 1.
  • If i % p == 0 (so p is already a factor of i): φ[i · p] = φ[i] · p. (Multiplying by an already-present prime multiplies n by p but doesn’t change the prime-power-removal structure.)
  • If i % p != 0 (so p is a new factor): φ[i · p] = φ[i] · (p - 1). (Multiplicative property: φ is multiplicative on coprime factors.)
def linear_sieve_with_totient(n: int) -> tuple[list[int], list[int], list[int]]:
    spf = [0] * (n + 1)
    phi = [0] * (n + 1)
    primes: list[int] = []
    phi[1] = 1
    for i in range(2, n + 1):
        if spf[i] == 0:
            spf[i] = i
            primes.append(i)
            phi[i] = i - 1
        for p in primes:
            if i * p > n:
                break
            spf[i * p] = p
            if i % p == 0:
                phi[i * p] = phi[i] * p
                break
            else:
                phi[i * p] = phi[i] * (p - 1)
    return spf, primes, phi

This is O(N) total — a free side effect of the linear sieve’s structure.

7.3 Möbius Function μ(n) for All n ≤ N

The Möbius function:

  • μ(1) = 1.
  • μ(n) = 0 if n has a squared prime factor.
  • μ(n) = (-1)^k if n is a product of k distinct primes.

By the same multiplicative argument:

  • If i is prime: μ[i] = -1.
  • If i % p == 0: μ[i · p] = 0 (squared prime factor introduced).
  • Else: μ[i · p] = -μ[i] (one more distinct prime, sign flips).
def linear_sieve_with_mobius(n: int) -> list[int]:
    spf = [0] * (n + 1)
    mobius = [0] * (n + 1)
    primes: list[int] = []
    mobius[1] = 1
    for i in range(2, n + 1):
        if spf[i] == 0:
            spf[i] = i
            primes.append(i)
            mobius[i] = -1
        for p in primes:
            if i * p > n:
                break
            spf[i * p] = p
            if i % p == 0:
                mobius[i * p] = 0
                break
            else:
                mobius[i * p] = -mobius[i]
    return mobius

μ is the heart of inclusion-exclusion arguments in number theory and combinatorics: counting coprime pairs, summing over divisors with sign-alternation, the Mertens function. Having μ(n) for all n ≤ N in O(N) time and space is the “free” sidecar to a linear sieve that turns competitive-programming problems involving divisor sums into one-line transformations.

7.4 Number of Divisors d(n)

Multiplicative recurrence: if n = i · p where p ∤ i, then d(i · p) = d(i) · 2 (one more prime to choose its exponent for: 0 or 1). If p | i, you need to track the exponent of p in i to update correctly. The bookkeeping is slightly more intricate than φ or μ but still O(N).

7.5 Sum of Divisors σ(n)

Similar multiplicative structure; same O(N) algorithm with careful exponent tracking.

8. Variants and History

8.1 The Gries-Misra Paper (1978)

A clean, widely-cited presentation of a linear sieve appears in Gries & Misra, CACM 1978, “A linear sieve algorithm for finding prime numbers,” which runs in time proportional to N and extends to producing the prime factorization of every integer in [2, N] in the same Θ(N) budget. The historical lineage is well established: Gries and Misra rediscovered a linear sieve that Leonhard Euler had already sketched in the 18th century (in the course of proving the zeta product formula Σ 1/n^s = Π_p (1 - p^{-s})^{-1}), where the construction “produces each composite from its prime factors only” and so eliminates each composite exactly once (Wikipedia — Sieve of Eratosthenes, “Euler’s sieve”). This is why competitive-programming sources (and this note’s title) call the algorithm Euler’s sieve, while academic credit for the first crisp linear-time analysis goes to Gries-Misra. Interestingly, the modern reference implementation on cp-algorithms does not cite Gries-Misra or Euler at all — it attributes its presentation to Paul Pritchard’s 1987 work — which is itself evidence of how tangled the attribution is.

A subtlety worth flagging precisely: the modern algorithm marks each composite by its smallest prime factor, and that is the version verified against cp-algorithms and Wikipedia. A symmetric largest-prime-factor formulation is algorithmically equivalent (same Θ(N) bound, inner loop iterating primes in the other direction), and is sometimes attributed to the original Gries-Misra treatment.

Uncertain

Verify: that the original Gries-Misra 1978 paper presents the largest-prime-factor variant (as §9.9 also claims). Reason: the primary PDF (cs.utexas.edu scanned copy) failed to fetch and the ACM Digital Library abstract returned HTTP 403 during this pass; secondary sources (cp-algorithms, Wikipedia) describe only the smallest-prime-factor version, so the largest-factor attribution is corroborated only by memory. To resolve: read the scanned Gries-Misra 1978 paper directly. Note: the smallest-prime-factor linear sieve presented in this note is fully verified and is not in doubt — only the historical “which variant did the 1978 paper use” detail is. uncertain

The asymptotically faster alternative is Pritchard’s wheel sieve (Pritchard 1981), an O(N / log log N)-time, O(√N)-space algorithm — the first sieve with running time sublinear in N — that uses wheel factorization to avoid even visiting numbers divisible by the smallest primes (Wikipedia — Sieve of Pritchard). It beats the linear sieve in operation count but, because of steep constant factors and an additive (rather than multiplicative) inner loop, rarely wins in wall-clock for the N ranges that arise in practice. The naming caution stands: “Euler’s sieve” is used in different communities for both this linear sieve and for the ancient Π_p (1 - 1/p) summation idea, so cite the algorithm, not just the name.

8.2 Pritchard’s Wheel Sieve

Pritchard’s 1981 paper presented an O(N / log log N) sieve via “wheel factorization”: skip multiples of 2, 3, 5, 7, ... up to a wheel modulus, then sieve only the residues coprime to the wheel. For N ≤ 10^9, the constant factor is steep and Pritchard’s sieve is rarely faster than a well-tuned segmented Sieve of Eratosthenes in practice. Asymptotically, however, it is the fastest known sieve.

8.3 Segmented Sieves

For N larger than RAM (~10^11 and up), the Sieve of Eratosthenes runs segmented — sieve [0, √N] first, then for each block [k · √N, (k+1) · √N], mark multiples using only the small-prime list. The linear sieve does not segment as cleanly because the inner loop’s i * p jumps far outside the current block. So for N > RAM, prefer the segmented SoE.

8.4 Bitset Optimizations

Both sieves can use a bitset (one bit per integer) instead of a byte array, giving 8× space reduction and often a 2× speedup from cache behavior. The linear sieve’s spf array, in contrast, needs at least 4 bytes per entry (to hold prime values up to N), so the bitset trick only applies to the “primality bool” version of the sieve.

8.5 Linear Sieve in Multiplicative-Function Land

Any multiplicative function f (one with f(ab) = f(a) f(b) for coprime a, b) can be computed for all n ≤ N in O(N) via the linear sieve, by augmenting the inner loop with the appropriate recurrence. Examples: φ, μ, d, σ, the Liouville function λ, the Jordan totient. Competitive-programming editorials for problems involving Σ_n f(n) g(...) regularly invoke this pattern.

8.6 Sieve of Atkin

Atkin’s 2003 sieve runs in O(N / log log N) and uses elliptic-curve number-theoretic identities. Has small constant-factor benefits in some implementations but is rarely beaten by Pritchard’s in benchmarks. Mostly of academic interest.

9. Pitfalls

9.1 Forgetting the Break

The single most common bug. Without if i % p == 0: break, the inner loop continues past p = SPF(i) and mis-marks i · p for primes p > SPF(i) — these multiples have a smaller prime factor, so we mark them with the wrong SPF, breaking factorization queries. The sieve still finds primes correctly (it only marks composites, never marks primes), but spf is corrupted.

9.2 Iterating Primes in the Wrong Order

The proof in §3 requires iterating primes in increasing order. The natural Python idiom for p in primes does this if primes is appended-to-end; for p in reversed(primes) would break the algorithm.

9.3 Off-by-One in the Bound i * p > n

The product i * p must be ≤ n to write spf[i * p]. The check if i * p > n: break is correct; if i * p >= n: break skips index n itself (incorrect when n is composite).

9.4 Initializing spf[1]

spf[1] has no defined value (1 has no prime factors). Sentinel-initialize to 0 and document the convention. Forgetting to special-case 1 in downstream code (e.g., factorization that loops while n > 1) is a common downstream bug.

9.5 Integer Overflow on i * p

For N near the language’s max integer, i * p can overflow before the bound check. In C, use int64_t for the product. In Python, no issue. In Rust, use checked multiplication or explicit u64.

9.6 Forgetting N + 1 in Array Size

spf and any per-i array must have size N + 1 to index [0, N] inclusive. Off-by-one here produces an IndexError on the last iteration.

9.7 Reaching for the Linear Sieve When SoE Suffices

For “list all primes up to N = 10^6” with no follow-up factorization queries, the SoE is simpler and often faster (in Python, by ~3×, due to slice-assignment vs interpreted inner-loop bookkeeping). Use the linear sieve when you need the SPF table for factorization, totient, Möbius, or other multiplicative function precomputes. Otherwise, SoE.

9.8 Misremembering Which Sieve Has Which Asymptotics

SieveTimeSpaceNotes
Sieve of EratosthenesΘ(N log log N)Θ(N) bitsComposite marked once per distinct prime factor
Linear (Euler / Gries-Misra)Θ(N)Θ(N) words for spfComposite marked once by SPF
Pritchard wheelΘ(N / log log N)Θ(N)Asymptotically fastest, complex
AtkinΘ(N / log log N)Θ(N)Elliptic-curve foundation, niche
Segmented SoEΘ(N log log N)Θ(√N)Cache-friendly, used for large N

Pre-empt the interview confusion by memorizing the first two rows.

9.9 Confusing “Smallest Prime Factor” with “Largest Prime Factor”

Some references (possibly the original Gries-Misra paper — see the flag in §8.1; and some Russian-language CP olympiad sources) use largest prime factor as the marker. Algorithmically equivalent, but the inner loop iterates primes in decreasing order with appropriate adjustments. The standard cp-algorithms presentation, and this note, use smallest. Don’t mix the two in one project.

9.10 Python Performance Trap

In CPython, the linear sieve can be slower than the SoE due to per-iteration interpreter overhead. If you need raw speed and have only the prime list (no SPF needed), from sympy import sieve or numpy-vectorized SoE often beats both hand-rolled sieves. Profile before optimizing.

10. Diagram — The Linear Sieve at Work, N = 12

flowchart TD
    Start["i=2 (prime); primes=[2]; spf[2]=2"]
    A["i=2, p=2: mark spf[4]=2; 2%2=0 → break"]
    B["i=3 (prime); primes=[2,3]; spf[3]=3"]
    C["i=3, p=2: mark spf[6]=2; 3%2≠0"]
    D["i=3, p=3: mark spf[9]=3; 3%3=0 → break"]
    E["i=4 (composite); spf[4]=2 already"]
    F["i=4, p=2: mark spf[8]=2; 4%2=0 → break"]
    G["i=5 (prime); primes=[2,3,5]; spf[5]=5"]
    H["i=5, p=2: mark spf[10]=2; 5%2≠0"]
    I["i=5, p=3: 5*3=15 > 12 → break (out of range)"]
    J["i=6 (composite); spf[6]=2 already"]
    K["i=6, p=2: mark spf[12]=2; 6%2=0 → break"]
    L["i=7..12: only outer-loop work; i*2 > 12 for i ≥ 7"]
    Done["Done. primes=[2,3,5,7,11]; spf populated."]

    Start --> A --> B --> C --> D --> E --> F --> G --> H --> I --> J --> K --> L --> Done

What this diagram shows. A linear-sieve trace up to N = 12. Each box is one outer-loop iteration i = 2, 3, 4, ... (and inner-loop steps within it). For each i, the algorithm first determines whether i is prime (by checking spf[i] == 0 — if so, i is prime; otherwise spf[i] was set in a previous iteration, so i is composite). Then the inner loop iterates primes p in increasing order, marks spf[i · p] := p, and breaks the moment i % p == 0 (equivalently, the moment p divides i, i.e., p ≥ SPF(i)). The “break” is what enforces the unique-marking property: composites past the SPF point would have a smaller prime factor than p, and the “by-SPF” rule reserves them for an earlier outer iteration. Trace each composite ≤ 12 to its (i, p) pair: 4 → (2, 2), 6 → (3, 2), 8 → (4, 2), 9 → (3, 3), 10 → (5, 2), 12 → (6, 2) — every composite marked exactly once, by the iteration whose i = c / SPF(c) and p = SPF(c). The Θ(N) bound is the count of those pairs (one per composite) plus a constant per outer iteration.

11. Common Interview / Competitive-Programming Problems

ProblemSourceWhat’s tested
List primes up to NclassicalLinear sieve or SoE
Factorize many numbers ≤ NclassicalSPF table → O(log N) per query
Sum of Euler’s totient over [1, N]classicalLinear sieve with totient recurrence
Number of squarefree integers ≤ NclassicalMöbius via linear sieve, then prefix sums
Number of pairs (i, j) coprime in [1, N]classicalΣ_d μ(d) · ⌊N/d⌋² — Möbius inclusion-exclusion
Count PrimesLC 204SoE typically; linear sieve overkill
Closest Prime NumbersLC 2523Sieve up to bound, linear-scan for closest
Largest Prime FactorLC variantsSPF table → divide repeatedly
Smallest Prime Factor of every n in [1, N]Codeforces / classicalDirect output of linear sieve
Mertens function valuesanalytic NTMöbius via linear sieve
GCD-sum problemsclassicalΦ via linear sieve

Linear sieve appears in every hard-difficulty number-theoretic problem above the “is N prime” tier; it’s a workhorse of olympiad-style competitive programming. In US-style coding interviews (Google/Meta/Amazon), it’s rare unless the role is specifically quantitative or systems-research-oriented.

12. Open Questions

  • Why does Pritchard’s wheel sieve (O(N / log log N)) rarely beat the linear sieve in practice for N ≤ 10^9? Hypothesis: the wheel introduces extra arithmetic per skipped composite that erases the asymptotic advantage. Empirical benchmarking on multiple architectures would clarify.
  • Is there an o(N) deterministic sieve? No, by an information-theoretic argument: any algorithm that outputs [is_prime[i] for i in 0..N] must perform at least Ω(N) work (N bits to write). Probabilistic sieves (Miller-Rabin, Miller-Rabin Primality Test) can test individual numbers in O(log^2 N) but don’t list all primes ≤ N in less than Ω(N) aggregate time.
  • When does cache-friendly segmented SoE beat the linear sieve in compiled code? Empirically, around N = 10^7 on commodity x86-64 with default page sizes; the SoE’s sequential bitset writes win out over the linear sieve’s scattered spf[i * p] writes. The crossover is implementation- and hardware-specific.
  • What’s the right linear sieve to use when N = 10^9 and RAM is bounded? Segmented SoE for primality, plus on-demand factorization (trial-divide each query by primes ≤ √N). The full SPF table for N = 10^9 would need ~4 GB; usually impractical.

The “marked exactly once, by its smallest prime factor” framing used throughout this note is the standard one and matches the canonical cp-algorithms treatment, which represents each number as i = lp[i] · x where x carries no prime factor smaller than lp[i] (cp-algorithms). An equivalent way to see linearity is a direct amortized count of the (i, p) pairs the inner loop actually visits — pairs with p ≤ SPF(i), of which there are at most one composite-marking step per composite plus one break step per i (the ≤ 2N bound in §6). The two arguments are duals: the SPF-ownership view assigns each composite a unique owner pair, while the amortized-count view bounds the total pairs visited. They reach the same Θ(N) conclusion.

13. See Also

Graph View

Backlinks