Engineering / Mathematics — The Distribution of Primes
The Sieve of Eratosthenes
The classical sieve for enumerating primes, its complexity, segmented variants, and its role as a precomputation step.
Executive summary
The sieve of Eratosthenes enumerates all primes up to a bound by repeatedly marking multiples of each prime found. It is optimal in practice for enumerating primes and is the standard precomputation for trial division tables.
Its memory requirement, not its time, is the binding constraint, which is what motivates the segmented variant.
Learning objectives
- State the algorithm and its time complexity.
- Explain the two standard optimisations.
- Describe the segmented variant and its memory profile.
01The algorithm
Sieve of Eratosthenes
bound Nall primes not exceeding N- Create a boolean array marked[2..N], all entries initially false.
- For i from 2 while i² ≤ N:
- If marked[i] is false, then i is prime:
- For j from i² to N in steps of i, set marked[j] = true.
- Return every index whose entry remains false.
O(N log log N) operations, O(N) bits of memoryTwo optimisations are built into the statement and both matter. Starting the inner loop at i² rather than 2i is correct because smaller multiples of i already carry a smaller prime factor and have been marked. Stopping the outer loop at √N is correct because a composite below N must have a factor below √N.
02Why log log N
The total work is the number of marking operations, which is the sum over primes p ≤ √N of N/p. By Mertens' theorem that sum is N ln ln N up to constants.
Σ_{p ≤ N} N/p = N · (ln ln N + M + o(1))03Memory and the segmented variant
The segmented sieve fixes this by processing the range in blocks that fit in cache.
Sieve the base
Find all primes up to √N with an ordinary sieve. This needs only √N bits.
Process segments
Divide [2, N] into blocks of size around √N or the cache size, whichever is smaller.
Mark within a block
For each base prime, mark its multiples inside the current block only, starting from the first multiple in range.
Emit and discard
Report the primes in the block and reuse the buffer for the next segment.
| Variant | Time | Memory | Notes |
|---|---|---|---|
| Plain | O(N log log N) | O(N) bits | Simple; memory-bound beyond about 10⁹ |
| Segmented | O(N log log N) | O(√N) bits | Cache-friendly; the practical choice |
| Wheel factorised | Lower constant | O(√N) bits | Skips multiples of small primes entirely |
| Linear (Euler) | O(N) | O(N) | Each composite marked once; slower in practice due to memory access |
The linear sieve is a curiosity worth knowing about: it achieves genuinely linear time by marking each composite exactly once, yet is usually slower than the segmented Eratosthenes sieve because its memory access pattern defeats the cache.
04Frequently asked questions
Is the sieve useful for testing a single large number?
No. Sieving to √n to test one n-bit number is exponential in the input length. The sieve is for enumerating many small primes; Miller-Rabin is for testing one large one.
What is the sieve typically used for in this subject?
Building the small-prime table used for trial division in prime generation, and constructing the factor base for index calculus and quadratic sieve factoring. Both need all primes below a moderate bound.
Why is the linear sieve slower despite better complexity?
Because it requires maintaining the smallest prime factor of each index and accesses memory in a less predictable pattern. On modern hardware the cache behaviour dominates the operation count.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 85-86.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.