Sieve of Eratosthenes
Instead of testing each number for primality, let the primes do the work. Walk upward: a number nobody has crossed out is prime, and its multiples are crossed out on the spot. Once the walk passes the square root of n, everything still standing is prime. The segmented sieve applies the same crossing-out to a window high up the number line: only the primes below the square root of the window's top can cross anything out, and the first multiple of each inside the window is found by rounding the window's start up to a multiple of it, so the memory needed is the width of the window rather than the size of the numbers.
Find the primes between 100 and 129 without touching the numbers below 100. A composite in this window must have a factor at most its square root, so every number that can cross anything out here is a prime at most 11: 2, 3, 5, 7, 11. Sieve those first, then use them on the window.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 5, with their answers.
Where does crossing out multiples of 2 start in this window?
Answer: 100. Round 100 up to the next multiple of 2: that is (100 + 2 - 1) / 2 * 2 = 100. Counting up from 2 would visit every multiple below the window.
Where does crossing out multiples of 3 start in this window?
Answer: 102. Round 100 up to the next multiple of 3: that is (100 + 3 - 1) / 3 * 3 = 102. Counting up from 3 would visit every multiple below the window.
Where does crossing out multiples of 5 start in this window?
Answer: 100. Round 100 up to the next multiple of 5: that is (100 + 5 - 1) / 5 * 5 = 100. Counting up from 5 would visit every multiple below the window.
Where does crossing out multiples of 7 start in this window?
Answer: 105. Round 100 up to the next multiple of 7: that is (100 + 7 - 1) / 7 * 7 = 105. Counting up from 7 would visit every multiple below the window.
Where does crossing out multiples of 11 start in this window?
Answer: 110. Round 100 up to the next multiple of 11: that is (100 + 11 - 1) / 11 * 11 = 110. Counting up from 11 would visit every multiple below the window.
How it runs, step by step
Find the primes between 100 and 129 without touching the numbers below 100. A composite in this window must have a factor at most its square root, so every number that can cross anything out here is a prime at most 11: 2, 3, 5, 7, 11. Sieve those first, then use them on the window.
Segmented sieve over 30 numbers from 100 to 129.
Prime 2: 100 divided by 2 rounds up to 100, so that is the first multiple of 2 in the window. Cross out 100 and every 2 after it: 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128.
2 crosses out 15 numbers from 100.
Prime 3: 100 divided by 3 rounds up to 102, so that is the first multiple of 3 in the window. Cross out 102 and every 3 after it: 105, 111, 117, 123, 129.
3 crosses out 5 numbers from 102.
Prime 5: 100 divided by 5 rounds up to 100, so that is the first multiple of 5 in the window. Cross out 100 and every 5 after it: 115, 125.
5 crosses out 2 numbers from 100.
Prime 7: 100 divided by 7 rounds up to 105, so that is the first multiple of 7 in the window. Cross out 105 and every 7 after it: 119.
7 crosses out 1 numbers from 105.
Prime 11: 100 divided by 11 rounds up to 110, so that is the first multiple of 11 in the window, but crossing starts at 121 because smaller multiples of 11 have a smaller prime factor. Cross out 121 and every 11 after it: 121.
11 crosses out 1 numbers from 121.
Every base prime has been used, so anything still unmarked has no factor at or below 11 and is prime: 101, 103, 107, 109, 113, 127.
6 primes in the window.
6 primes between 100 and 129, found with 30 flags in memory instead of 129. That is the whole point: the window can sit anywhere, even near a billion, as long as the base primes up to its square root fit. Sieving a huge range in windows like this also keeps each pass inside the processor cache, which is why it is faster in practice as well as smaller.
6 primes found between 100 and 129.
Write it yourself
Define countPrimes(n) and return how many primes there are up to and including n. It runs in your browser against this lesson's own 3 examples.
// Mark the multiples of each prime, starting at its square because everything below it is already marked.function countPrimes(n) { return 0;}
Remember
- An unmarked number is prime because every smaller prime already crossed out its own multiples.
- Start crossing at p x p: smaller multiples of p have a smaller prime factor and are already gone.
- Stop once p x p is past n. Segmented: base primes up to sqrt(high), first multiple at ceil(low / p) * p, memory is the window width.
Topics covered
Where this is used
CryptographyGenerating RSA and TLS keys
OpenSSL does not hand a fresh 2048-bit candidate straight to Miller-Rabin. BN_generate_prime_ex draws one random odd number, then walks upward in steps of two and rejects every offset that a prime from a compiled-in small-prime table divides, which is this algorithm's crossing-out run over a window of odd numbers. It stores the candidate's residue modulo each small prime once, so testing the next offset is an add and a remainder on machine words rather than a big-number division. At 2048 bits it uses the first 384 entries of that table, topping out at 2657, and that kills roughly six candidates in seven before a single Miller-Rabin round runs.
Developer toolsprimesieve
primesieve, the open source tool used to generate and count primes past 10^18, is a segmented sieve whose segment is sized from the CPU cache sizes it measures at startup. Crossing out multiples is a scattered write pattern, so a sieve array larger than cache spends its time waiting on memory rather than doing arithmetic. Keeping the working set resident is the whole point of the segment, which is the same idea as the segmented version here applied to cache instead of RAM.
CryptanalysisThe sieving phase of integer factorization
The quadratic sieve and the general number field sieve, the algorithms behind every public RSA factoring record, spend most of their runtime in a loop identical in shape to this one: for each prime in a factor base, find the positions in the current interval that it divides, then step forward by p and mark. The mark is an added log p rather than a boolean, and a position whose marks sum close to the size of the value sitting there is a candidate that factors completely over the factor base. Making that crossing-out loop faster is what moves the record.
Scientific computingSymPy's prime generator
sympy.sieve is a sieve of Eratosthenes that grows on demand: a lookup past the sieved range extends the sieve out to the number asked for and keeps the result, so a session that asks for primes repeatedly pays the cost once rather than per call. The same object backs sympy's totient and Mobius range functions, because both are computed by walking each prime and touching its multiples. That is this algorithm's inner loop with a different value written at each step instead of a flag.
Why it works this way
Why n log log n and not n log n?
For each prime p the inner loop writes about n / p flags, so the total number of writes is n times the sum of 1 / p over the primes up to n. That sum grows like log log n, which is under 4 even at n = 1,000,000,000. The sieve therefore does only a few passes' worth of writes over the array, which is why it behaves like a linear scan in practice.
When a primality test beats the sieve
The sieve is the right tool when you want every prime below a bound, because each number costs a handful of array writes and nothing else. It is the wrong tool for one large candidate: deciding whether a single 2048-bit number is prime takes milliseconds with Miller-Rabin, while sieving up to it would need more memory than exists. Cost here scales with the width of the range, not with the size of the number you care about.
p x p overflows long before n does
The stop test is written p.toLong() * p > n deliberately. In 32-bit arithmetic p * p wraps once p reaches 46,341, because 46,341 squared is just past Int.MAX_VALUE, and the wrapped value is usually negative, so the comparison is false, the loop never breaks, and the inner range then starts at a negative index. Widening that one multiplication, or comparing p > n / p instead, removes the trap; this is the same class of bug as (low + high) / 2 in binary search.
Why the segment start takes a max against p x p
The start position is max(p x p, the first multiple of p at or after low), and the max is what stops a base prime from crossing itself out. If the window sits low enough that p itself falls inside it, rounding low up to a multiple of p lands exactly on p, and p gets marked composite. The rounding is written (low + p - 1) / p * p so it stays in integer arithmetic instead of going through a float. The separate it > 1 filter covers the other low-end edge case: no start position is ever below 4, so 0 and 1 are never crossed out by anything and would otherwise be reported as prime.
Read more
- Sieve of EratosthenesWikipedia
- Sieve of Eratosthenes, with the segmented version and the complexity proofcp-algorithms
- Linear sieve: O(n) with a smallest prime factor tablecp-algorithms
- The Genuine Sieve of EratosthenesMelissa E. O'Neill, JFP 2009 · cs.hmc.edu
- primesieve: segmented sieve tuned to the CPU cacheprimesieve · github.com