If many queries ask for the prime factors of integers bounded by the same limit, repeating trial division wastes work. We can first record the smallest prime factor of every integer in that range, then factor each query by repeatedly looking up and removing one prime.
The sieve here is called linear because its total number of generated composites is linear in the limit. A nested loop does not automatically make an algorithm quadratic: the useful question is how many pairs the loop actually visits. We will assign each composite exactly one generating pair and prove that the stopping rule preserves that assignment.
Define what each table entry means
Definition 17.2.1
(Smallest prime factors and marker entries)
A prime is an integer greater than one with no positive divisors other than one and itself. For , let be its smallest prime divisor. Such a divisor exists: the least divisor greater than one must be prime, otherwise one of its smaller factors would also divide .
For an integer limit , the table has indices . After construction, spf[x] is for . Entries at zero and one remain zero as markers; zero is not being called their prime factor. One has the empty prime-factor list.
During construction, a zero at an index at least two means “not marked yet.” It means “prime” only when the outer loop reaches that index and the correctness invariant justifies the conclusion. We must not interpret all initially zero entries as primes.
Generate a composite from a processed integer and a prime
Process in increasing order. Maintain an increasing list of primes discovered so far. If spf[i] is still zero, set it to and append to that list. Then visit primes in increasing order, generating , but only while
For each allowed pair set spf[i*p] = p. The first restriction is essential to the unique-generation proof. The second stays inside the precomputed range. In the implementation, test p > N // i before forming the product, so even an unwanted oversized product need not be evaluated.
Theorem 17.2.2
(Unique generation and completeness of the sieve)
Let . In the construction above:
- every pair that the loop writes satisfies , and is composite;
- every composite is written exactly once, by the pair ;
- an index is still unmarked when the outer loop reaches it if and only if is prime.
Hence at the end spf[x] equals for , and the prime list holds exactly the primes up to , in increasing order.
Proof
(Smallest factor, canonical pair and the prime test)
Statement 1. For an allowed pair, every prime factor of is at least . The number is itself prime and divides . Thus is the smallest prime factor of , and is composite because .
Uniqueness in statement 2. If a composite were generated by two allowed pairs, statement 1 shows that both prime components equal . Their other components would then both equal , so the pairs are identical. No composite is written twice.
Existence in statement 2, together with statement 3. Use induction on the outer-loop index. Let and assume that every index below has been classified correctly, with the right value in spf, when the loop reaches . If is composite, let and , so . No prime smaller than divides , because it would also divide ; hence . Prime is therefore already in the list, or equals and has just been appended. Every earlier prime in the inner loop also satisfies the factor bound and has product at most , so neither stopping rule prevents the loop from reaching . The pair writes at the smaller index , before the loop reaches . If is prime, statement 1 shows it is never written, because every written index is composite. So is unmarked when reached, is appended to the list, and receives . Starting the induction at two completes the table. ∎
Proof X-ray
What each restriction buys in the sieve proof
The factor restriction does two jobs that point in opposite directions. Read forward, it makes the smallest prime factor of , so every write stores the right value and no composite can be reached by a second pair. Read backward, the canonical pair always satisfies it, so nothing is lost. The bound plays no part in either job; it only keeps writes inside the table, and the proof checks it once, for .
The one non-obvious move is that the induction runs on the outer index and uses : the cofactor of a composite is always processed before the composite itself. That ordering is why the prime test needs no separate step. A number that is still unmarked when its turn comes cannot have a canonical pair left to arrive, so it is prime. The first half of the proof guarantees that a write is correct and unique; only the second half shows that no composite is missed.
Trace the table at a small limit
Worked example 17.2.3
(Every composite through twelve has one generating pair)
For , construction produces:
| x | Smallest prime factor | How x is classified |
|---|---|---|
| Unmarked when reached: prime | ||
| Unmarked when reached: prime | ||
| Generated by | ||
| Unmarked when reached: prime | ||
| Generated by | ||
| Unmarked when reached: prime | ||
| Generated by | ||
| Generated by | ||
| Generated by | ||
| Unmarked when reached: prime | ||
| Generated by |
At , prime 2 generates 6 and prime 3 generates 9. At , the smallest factor is two, so prime 3 is not allowed to generate 12. The canonical pair for 12 comes later as , still before outer index 12.
Counterexample mode
Stopping after one prime can classify nine incorrectly
Suppose a modified loop always stops after its first generated product. At , it generates 6 using prime 2, then never reaches prime 3 to generate 9.
The only possible allowed canonical pair for 9 is . If it is omitted, 9 is still unmarked when reached and is incorrectly appended as a prime. Composite outer indices often stop at their smallest prime, but that is not a reason to stop every outer index after its first prime.
The first example removes an iteration; the second removes a restriction.
Counterexample mode
Removing the factor restriction destroys uniqueness, not automatically every final value
If we permit primes larger than spf[i], 12 can be generated at and again at . The first assignment uses three, even though the smallest factor is two.
A later assignment may repair that value, so this example alone does not prove the final table of that altered algorithm is wrong. It does prove that the one-generation-per-composite argument no longer applies. A different loop needs its own correctness and complexity analysis; it cannot inherit the linear bound just because its code looks similar.
Build the table, then follow its factor links
The inputs are integers as a type precondition. The constructor checks . Factor extraction checks that its argument lies between one and the table's limit. It assumes the table is an unchanged correct SPF table from construction; it does not revalidate arbitrary supplied entries.
def smallest_prime_factors(limit):
if limit < 1:
raise ValueError("the limit must be at least one")
spf = [0] * (limit + 1)
primes = []
for value in range(2, limit + 1):
if spf[value] == 0:
spf[value] = value
primes.append(value)
for prime in primes:
if prime > spf[value] or prime > limit // value:
break
spf[value * prime] = prime
return spf, primes
def factorize_from_spf(value, spf):
if not 1 <= value < len(spf):
raise ValueError("the value must lie between one and the table limit")
factors = []
while value > 1:
prime = spf[value]
factors.append(prime)
value //= prime
return factors
smallest_prime_factors(12) returns the displayed factors with marker entries at 0 and 1, together with prime list [2,3,5,7,11]. A limit of one is valid and gives [0,0] and no primes. Building a table through 100 and calling factorize_from_spf(84, spf) returns [2,2,3,7].
Prove what factor extraction returns
Proposition 17.2.4
(Factor extraction by repeated lookup)
Let spf be the correct table through and let . Then factorize_from_spf(x, spf) returns a nondecreasing list of primes whose product is . It performs one lookup and one exact division per entry, and the list has at most entries.
Proof
(An invariant on the current quotient)
Let the current quotient be and the emitted list be , with its th entry. Maintain
Initially the empty product is one and . For , the table supplies a prime dividing . Appending and replacing by preserves the equality. Because , the quotient strictly decreases, so the loop ends with ; then the emitted primes have product exactly .
The list is nondecreasing. If a prime smaller than the chosen smallest factor divided the next quotient , it would also divide , contradicting the smallestness of . Repeated copies of one prime record its multiplicity.
If entries are emitted, each is at least two, so and . The value one has , and a value attains equality by emitting copies of two. ∎
Worked example 17.2.5
(Factor eighty-four while retaining a checkable certificate)
The successive quotients are , and the emitted factors are . Their product is . Grouping equal factors gives the compact notation .
At quotient 21 the next lookup is three, not two. The table is indexed by the current quotient, not repeatedly by the original input. One returns an empty list because the empty product is one; zero is outside this factor-extraction contract.
Worked example 17.2.6
(Boundary limits and a prime query)
For the outer loop range(2, 2) is empty, so the construction returns [0,0] and no primes; factoring one then returns []. For the loop reaches with spf[2] zero, sets it to two and appends two. The inner loop then tests prime two: is false, but is true, so it stops. The result is [0,0,2] with primes [2]. In a table through , the query finds spf[97] equal to , emits , and the quotient becomes one: a prime returns a one-element list.
Common mistake
(Reading every zero entry as a prime)
While the table is being built, an index at least two that still holds zero is only unmarked. At the moment the outer loop begins , the entry for is still zero although is composite; it is written during that very iteration, by the pair . A zero may be read as "prime" only when the outer loop itself reaches the index, because by then its canonical pair has had its turn.
Common mistake
(Looking up the original input instead of the current quotient)
Suppose extraction divides the quotient but keeps reading spf[84]. It emits two at quotient , again at , and again at , where two does not divide and 21 // 2 silently truncates to . The loop then keeps emitting two at , and , ending with six copies of two whose product is , not . The lookup must use the current quotient, as the invariant above requires.
Explain why the nested construction is linear
Each successful inner iteration writes one composite. The unique-generation proof bounds these successful iterations by the number of composites through , hence by . Each outer iteration can additionally have at most one terminating failed check: it breaks immediately. Prime detection and outer-loop overhead also occur only times.
Concept lensCombinatorial
The sieve as a tree on the integers
Join each to . This is a tree on rooted at , because the parent is smaller. The children of are the products with prime and (any prime when ), and for the sieve writes exactly these edges when the loop reaches ; the edges from lead to the primes, which the loop finds unmarked. A tree on vertices has edges, which is the linear count. Factor extraction walks from up to the root; the edge labels are the emitted primes.
Therefore preprocessing uses arithmetic/array operations, assuming the usual constant-word access and amortized constant-time append model for the prime list. This proof does not estimate the number of primes or sum their reciprocals. It charges work to the canonical composite writes and the terminating checks.
The SPF array and prime list use stored entries, even though many entries are composite. That is a cell bound, not an -bit claim: the stored integers may need bits each. Likewise division, multiplication and comparison carry their bit costs when integers are not treated as machine words. Python integers preserve the arithmetic, while a fixed-width port must size indices and calculations appropriately. The division-based product guard avoids evaluating an out-of-range product before rejecting it.
After preprocessing, factor extraction costs one lookup and one exact division per emitted factor, plus constant overhead. Across queries it performs such operations and emits prime entries. Writing binary integers also has output-bit cost; the list-operation bound does not erase it.
Precomputing every integer through a huge limit is not automatically worthwhile for a single query. The dense table costs time and memory proportional to the limit, irrespective of how few values will be factored. Its strength is sharing that work among many bounded queries. Other workloads need different choices and analyses; this lesson does not claim a universal best factorization method.
Exercises and worked solutions
Quick check
(1. Explain why nine is marked before it is visited)
For limit twelve, which outer value and prime generate nine? Why would a rule that always stops after its first prime fail here?
Solution · Solution 1
Outer value three and prime three generate nine. At that outer value, prime two first generates six, but three is also allowed because spf[3] equals three. Stopping after the first prime would leave nine unmarked and later misclassify it as prime.
Quick check
(2. Identify the canonical pair rather than any factor pair)
Why does the linear sieve generate twelve as and reject ? Does allowing both pairs alone prove that the altered algorithm's final table must be wrong?
Solution · Solution 2
Two is twelve's smallest prime factor, so the canonical quotient is six. For outer value four, spf[4] is two and prime three exceeds the allowed bound. Allowing both loses unique generation; a later two assignment may repair the earlier three. The final-value behavior and runtime of that altered method need separate proofs.
Quick check
(3. Check a returned factor list against the loop invariant)
Factor eighty-four using the current quotient at each step. Give all quotients, the factor list and the product certificate. Why should a factor two not be taken again at quotient 21?
Solution · Solution 3
Quotients are and factors are , whose product is 84. At every step emitted-product times quotient equals 84. The current lookup at 21 is three, and two does not divide 21; repeatedly reading the original entry would violate the invariant.
Quick check
(4. State what marker values do and do not mean)
What does factor extraction return for one? Is spf[1] = 0 a claim that zero is prime? Which assumptions are required if a caller supplies a table rather than building one immediately before the call?
Solution · Solution 4
One returns [], representing the empty product. Zero is only a marker at indices zero and one, not a prime. Extraction requires an unchanged correct SPF table and an integer query within its range; it does not prove arbitrary supplied entries correct. Zero, negative queries and queries beyond the limit are rejected.
Quick check
(5. Count all inner iterations and the right kind of storage)
Why does a nested loop still take linear word-operation work here? What accounts for an iteration that stops without generating a composite, and why is entries not automatically bits?
Solution · Solution 5
Each successful iteration belongs to one distinct composite, so there are at most . Each outer iteration has at most one failed terminating check, adding another . Stored integers may each need bits, so linear entry count and linear bit storage are different statements. Arithmetic costs also depend on the numeric model.
Quick check
(6. Match query output length to the preprocessing decision)
For a query , how many factors are emitted? If only one large x is needed, does this short output bound justify allocating a table through x?
Solution · Solution 6
It emits copies of two, attaining the logarithmic factor-count bound. That does not remove the preprocessing and stored-entry cost of a dense table through . The output size and the cost of preparing all possible bounded queries must be assessed separately.