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 every prime up to 30. Start at 2 and walk upward. A number nobody has crossed out is prime, and its multiples get crossed out. 1 is not prime by definition, so it is out from the start.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 4, with their answers.
Next is 2. Prime or composite?
Answer: Prime, nothing smaller divides it. Every prime below 2 already crossed out its multiples, and none of them hit 2.
Next is 3. Prime or composite?
Answer: Prime, nothing smaller divides it. Every prime below 3 already crossed out its multiples, and none of them hit 3.
Next is 4. Prime or composite?
Answer: Composite, already crossed out. 4 was crossed out earlier, which is exactly what makes it composite.
Next is 5. Prime or composite?
Answer: Prime, nothing smaller divides it. Every prime below 5 already crossed out its multiples, and none of them hit 5.
How it runs, step by step
Find every prime up to 30. Start at 2 and walk upward. A number nobody has crossed out is prime, and its multiples get crossed out. 1 is not prime by definition, so it is out from the start.
Sieving the numbers 1 to 30. 1 is crossed out to begin with.
2 is still unmarked, so no smaller number divides it: prime. Cross out its multiples from 4 on: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30. Smaller multiples like 4 were already crossed by a smaller prime.
2 is prime. 14 multiples are crossed out.
3 is still unmarked, so no smaller number divides it: prime. Cross out its multiples from 9 on: 9, 15, 21, 27. Smaller multiples like 6 were already crossed by a smaller prime.
3 is prime. 4 multiples are crossed out.
4 is already crossed out, so it is composite. Its multiples were handled by whichever prime crossed it. Skip.
4 is composite and is skipped.
5 is still unmarked, so no smaller number divides it: prime. Cross out its multiples from 25 on: 25. Smaller multiples like 10 were already crossed by a smaller prime.
5 is prime. 1 multiples are crossed out.
Past 6, p x p is more than 30, so no prime left can cross out anything new. Every number still unmarked is prime: 7, 11, 13, 17, 19, 23, 29.
The remaining unmarked numbers are all prime: 7, 11, 13, 17, 19, 23, 29.
10 primes up to 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Each composite was crossed out by its smallest prime factor, and the work is about n log log n, far below testing every number.
10 primes found up to 30.
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