Motivation
Why list primes at all?
Many computations need a list of every prime up to a bound , not a verdict on one integer. Examples include factoring many small numbers, tabulating arithmetic functions, and testing conjectures on an initial range. Testing each integer separately repeats work: the facts that and both come from the single prime . The sieve of Eratosthenes reverses the direction of the question. It does not ask what divides . It asks, for each small prime , which numbers divides.
The aim of this chapter is a list we can call certified: a deterministic, finite procedure together with a proof that, for every integer with , the procedure reports as prime exactly when is prime.
Definitions
Primes, composites, and the two exceptional integers
Definition 9.1.1
(Prime, composite and least prime factor)
An integer is prime if and its only positive divisors are and . An integer that is not prime is composite. Equivalently, is composite when for integers with .
The integers and are neither prime nor composite. Every integer divides , so has no restricted divisor structure. The integer is a unit, and if it were prime, unique factorization would fail, since . A sieve must therefore classify and explicitly. They are excluded by definition, and crossing out multiples of primes never reaches them.
For , write for the least prime factor of . It exists because has a prime factorization. Note that exactly when is prime.
Lemma 9.1.2
(Small prime divisor)
If is composite, then . In particular, every composite has a prime divisor with .
Proof
(Factor a composite)
Write with . Then . Since , the integer has a prime factor , and . Because divides and divides , the prime divides . Hence , and so . If in addition , then , proving the stated consequence.
We also need a small arithmetic fact. For integers and ,
If , then , and since is an integer, . Conversely, gives . The right-hand form matters on real machines because it never computes a product that might overflow.
The algorithm and its machine model
Model. We work on a word machine whose words hold the integers , for an integer . Addition, subtraction, multiplication, floor division, comparison, and array access on words each cost one step. There is also a largest array length that can actually be allocated. Integers are not unlimited and memory is not unlimited. The input must satisfy the precondition
When the array is allocated, it needs cells because the indices run over . Check the length condition without overflowing: for example, use a wider length type, or compare when . If the stated precondition fails, the procedure must refuse; it must not wrap around silently. It is a sufficient contract, even though the two early-return cases need no array.
Common mistake
(Allocating cells instead of )
The indices run over , so the array needs cells. With only cells the index is lost: for the final write falls outside the array, and for a prime input such as the largest prime is never reported.
SIEVE(N)
require 0 ≤ N, N fits in a word, and N + 1 cells can be allocated
if N ≤ 1: return empty list
allocate mark[0..N] # N + 1 boolean cells
for k := 0 to N: # stop after k = N; never form N + 1
mark[k] := (k ≥ 2)
p := 2
while p ≤ floor(N / p): # same as p*p ≤ N, but cannot overflow
if mark[p]:
m := p * p # safe: p*p ≤ N
loop:
mark[m] := false
if m > N - p: exit loop # the next multiple would exceed N
m := m + p # safe: m + p ≤ N
p := p + 1
return all k with 0 ≤ k ≤ N and mark[k] = true
Overflow audit. For the procedure returns before forming . For , all word-valued indices and arithmetic intermediates listed below lie in ; the allocation length is checked separately:
- ;
- is computed only after has been established;
- because ;
- is formed only when ;
- whenever executes, we have , so .
Thus these word-valued computations never need a number larger than . A length type may still have to represent .
Correctness
For the remaining proof suppose . Let , the largest integer with . By the equivalence above, the outer loop processes and stops at .
Lemma 9.1.3
(Invariant )
Just before the loop condition is tested with the value :
(a) is true for every prime ;
(b) and are false (when those indices exist);
(c) is false for every composite with .
Proof
(Induction on )
Base case, . Initialization sets entries with to true and to false, which gives (a) and (b). Part (c) is vacuous, because every least prime factor is at least .
Step. Assume holds and that the body runs, so .
Case 1: is composite. By the small-prime-divisor lemma, , so (c) says is false, and the body changes nothing. A composite with cannot have , because is not prime. So it already satisfies , and follows from .
Case 2: is prime. By (a), is true. The inner loop starts at and steps by . It exits exactly when the next value would exceed . So it crosses out exactly the multiples of in .
Each such number is with , so it is composite and at least . No prime and neither of is touched, so (a) and (b) survive.
For (c), let be composite with . Write . Since , we have , and every prime factor of divides and is therefore at least . Hence and , so was just crossed out. Together with , this gives .
Theorem 9.1.4
(The sieve certifies its list)
For every integer satisfying the precondition, terminates and returns exactly the primes with .
Proof
(Termination, soundness and completeness)
Termination holds because increases by in each outer iteration, and each inner loop strictly increases , which is bounded by . At exit, holds.
Primes are reported by (a), and are not reported by (b). Now take a composite . By the small-prime-divisor lemma, , so . Then (c) shows that is not reported.
For , the early return is the empty list, which is correct because there are no primes below . For or the loop never runs, which is correct because no composite exists.
Proof X-ray
How the invariant certifies the whole list
The small-prime-divisor lemma is used twice. In the inductive step it shows that a composite is already crossed out, so the body changes nothing; in the completeness step it shows that every composite has .
The key move is to index part (c) by least prime factors. When a prime is processed, the only composites newly required by (c) are those with , and each is with . That is why the inner loop may start at : a multiple with has a prime factor of below and is already false by . Starting at would also be correct, but it would only repeat work.
The argument closes only because the loop runs up to , so that covers every least prime factor at most . A guard breaks exactly this when for a prime : the loop stops at , and , the only composite in with least prime factor , stays unmarked. During the run a true entry means only “not yet crossed out”; entries above are never examined as and are certified by the completeness step alone.
Worked examples
Worked example 9.1.5
(A complete trace for )
Here . The array has cells, for the indices .
| test | crossed (new entries in bold) | ||
|---|---|---|---|
| 2 | true | 4, 6, 8, …, 48 (all 23 new) | |
| 3 | true | 9, 12, …, 48; new: 9, 15, 21, 27, 33, 39, 45 | |
| 4 | false | — | |
| 5 | true | 25, 30, 35, 40, 45; new: 25, 35 | |
| 6 | false | — | |
| 7 | true | 49 only; new: 49 | |
| 8 | fails | — | stop |
For , the guard reads , so the inner loop exits after one write, and is never formed.
Before is processed, the unmarked entries are the primes together with . At that moment, being unmarked does not certify primality.
The final list is
As a check, the new crossings total . The interval contains integers, and of them are composite, as required.
Concept lensCombinatorial
Counting the survivors by inclusion–exclusion
The integers in divisible by no prime are and the primes in : the entries the sieve leaves unmarked, apart from the sieving primes themselves. Inclusion–exclusion over the sieving primes counts them without listing them:
where runs over products of distinct primes at most , including , and is the number of those primes. For the sixteen terms total : the integer and the eleven primes from to .
Worked example 9.1.6
(Moving across )
Take . Then , so the loop processes and stops because fails. The prime is never used as a sieving prime, yet it is correctly reported. No composite up to has least prime factor , since the smallest such number is . The output is .
Now take . The test succeeds, so crosses out . For the outer-loop values and sieving primes are the same, and also crosses out .
Which sieving primes are needed depends on through . It does not depend on the largest prime in the output.
Worked example 9.1.7
(One input, )
Suppose we only want to know whether is prime. Since , the small-prime-divisor lemma says it suffices to try the divisors .
The divisors through all leave a remainder, and divides , because . This takes divisions and a constant number of words of memory.
Sieving to would allocate cells to answer this one question. A middle option is to sieve only to and then trial-divide by the primes up to .
The sieve is designed to reuse work when answers for many integers are needed; the practical crossover depends on the implementation and workload.
Cost
Storage. The array has boolean cells, which is . Beyond that, only a constant number of words is used, plus the output list.
Time. Initialization and the final scan each take steps, and the outer loop runs at most times. The remaining work is the crossing-out, which we now bound.
Theorem 9.1.8
(Elementary time bound)
For , the number of executions of is at most . Hence uses steps in the word model.
Proof
(Sum the writes over the sieving primes)
A prime makes
writes, because . Summing over all integers , which only adds terms, gives at most , where .
Next we show . Let , so that . For , the block contains integers, each with , so each block contributes at most . Together these full blocks cover ; the last may extend past , and including its extra positive terms only enlarges the upper bound. Hence .
For there are writes, against the bound . Sharper estimates of the form exist, but they rely on facts about sums of reciprocals of primes that are not proved here, and nothing in this chapter depends on them.
Bit complexity. Value and size are different measures. For , set . The array cells are exponential in the binary input length . In a bit-cost RAM where indexed array access and address handling each cost at most bit operations, and arithmetic on -bit integers uses schoolbook methods, including multiplication and division at each, the preceding word-operation count gives the conservative bound bit operations. This is an upper bound, not a sharp analysis. A packed marking array uses bits, with bits for a constant number of counters; a separately stored output list needs additional space. The word-cost model alone does not imply these bit costs, and this is not a single-tape Turing-machine bound.
Alternatives. Trial division of a single takes at most divisions. Applying trial division to every costs at most divisions. Dividing by every instead costs . These elementary upper bounds are larger than the sieve bound; that comparison alone does not establish a practical runtime ordering for every input.
Segmenting (optional idea). To list the primes in with :
- first sieve the base primes up to ;
- then, using an array for the window only, cross out for each base prime the multiples from to .
Correctness follows from the small-prime-divisor lemma and the same argument as before. Starting at ensures that a base prime lying inside the window is not crossed out. For a single requested window this can save both storage and work compared with sieving the whole range; enumerating all windows still requires processing every window.
Enumeration is not a primality test
A probabilistic primality test, such as the Miller–Rabin test, solves a different problem.
- Input. A single , often hundreds of digits long. The sieve instead takes a bound and treats every .
- Cost. The test's running time is polynomial in . The sieve's memory is linear in the value , which is impossible for large .
- Guarantee. When the test reports "composite", it has found a witness that can be checked. When it reports "probably prime", the result is backed only by a probability bound from the test's analysis, which is not proved here. That answer is not a proof of primality. The sieve's output is unconditional, by the certification theorem.
- What can be checked. A sieve's claim that is composite can be checked by one division, if we record the prime that crossed out. Its claim that is prime rests on the completeness argument: every prime that could witness compositeness was used.
Deterministic polynomial-time primality tests also exist, but they belong to a separate theory.
Counterexample mode
Misconception: an unmarked entry is prime, or the loop may stop at p squared below N
Claim A. "Once an entry has survived the sieve for a while, it is prime."
Counterexample. With , after have been processed, the entry is still unmarked, yet .
Claim B. "The guard suffices."
Counterexample. For , the loop stops before , and is reported as prime.
Diagnosis. The certificate is the final invariant , and it requires .
Exercises
Quick check
(For and , list the sieving primes that are actually used. Explain what the guard would report for .)
Solution
Since , we have for . The loop processes , and the sieving primes are .
For , , so also runs and crosses out alone, since ends the inner loop.
The composite is the only composite up to with least prime factor , by the square-boundary remark. Under the strict guard the loop stops at , so stays unmarked and is falsely reported as prime.
Quick check
(For , count the crossing writes exactly. Count the composites in , and explain the difference.)
Solution
Each sieving prime makes writes:
| writes | |
|---|---|
| 2 | |
| 3 | |
| 5 | |
| 7 | (since ) |
The total is writes.
There are primes up to . The interval contains integers, so it contains composites. The difference is repeated writes.
To confirm, count the numbers crossed by more than one prime:
- by both and (from on): , which is numbers;
- by and : ;
- by and : ;
- by , and : only .
By inclusion–exclusion, distinct composites are crossed out, which agrees with the count above.
Quick check
(Compare mathematical variants which mark all multiples of in or in , using an empty range when the lower endpoint exceeds . Show that the first gives the same output and the second is wrong; find the smallest that fails. Explain why directly changing the starting value in the do-then-guard pseudocode is not a safe implementation of the second variant.)
Solution
Starting at writes a superset of the original crossings. Every additional write is a multiple with , hence composite. So (a) and (b) still hold, and (c) still holds because the original writes are included. The output is unchanged.
Starting at , the number is never crossed by . Its only prime factor is , so no other prime crosses it either. For the loop runs only with and crosses nothing, so is reported as prime. For no composites exist, so is the smallest failure of this mathematical variant. Directly substituting into the displayed do-then-guard loop is even worse: at , it first attempts to write index outside the array. An implementation must check the starting value before writing, without overflowing when it computes that value.
Quick check
(On an -bit machine with words , suppose the naive operations wrap modulo and take . In two separate experiments replace only the guarded outer test by “”, or only the guarded inner update by “ while ”; keep the other part guarded. Show what goes wrong in each experiment. Then check the fully guarded version.)
Solution
With the naive inner loop and , the value steps to . Since , the loop never ends.
With the naive guard, gives , so the loop continues. Then gives . Because is true, the inner loop starts at and crosses out . But is prime, so its array entry is falsely marked composite; the overflowed loop need not terminate at all.
The guarded version tests , which fails, so the loop stops correctly with .
There is a separate length issue: does not fit in an 8-bit word. If the allocation interface cannot represent that length, the precondition fails and the procedure must refuse. If lengths use a wider type and , the stated precondition permits ; the guarded word computations are then safe. In neither case may an overflowing length be silently wrapped.
Quick check
(Explain why sieving to and running a probabilistic test on one give different kinds of answers, even when both say “prime”.)
Solution
The sieve requires cells, which may exceed the allocation limit . If it runs, the certification theorem certifies the status of every .
The probabilistic test handles a single , with a cost polynomial in about bits of input. Its answer "probably prime" carries an error bound, not a proof.
The two procedures answer different questions with different guarantees. The sieve answers "which are prime?" with a proof. The test answers "is this prime?" with high confidence.
Related notes
Prerequisites are divisibility, strong induction (used in the induction on ), and prime factorization (used for the existence of ). Natural continuations are least-prime-factor sieves and trial division with a sieved list of primes.