Sieve of EratosthenesPrime sieves
Cross off multiples from the bottom up.
Used for: Generating a prime table, factorisation
01Why it exists
Generating a 2048-bit RSA key means drawing large odd numbers at random and testing each one for primality. Every run of a probabilistic primality test costs a modular exponentiation over thousands of bits, which is expensive — and most of the odd numbers drawn at random turn out to have a tiny factor.
Why this fitsLibraries such as OpenSSL ship a table of the first few thousand small primes. A candidate is trial-divided by those first, anything divisible is discarded on the spot, and only the survivors reach the expensive probabilistic test. That table of small primes is exactly what a sieve produces, and most candidates are eliminated at this gate, saving a great deal of wasted modular exponentiation.
An analytics job has to count the divisors of a million integers, none of them larger than 10⁷, and every one has to be factorised first. Trial-dividing up to √x costs more than three thousand divisions for a single bad number, which adds up to billions of operations in the worst case.
Why this fitsBuild a table of smallest prime factors, spf, with a linear sieve in O(N) time. After that, factorising x is just repeatedly dividing by spf[x], and since every step at least halves the number, one factorisation takes O(log x) steps. A table for a limit of 10⁷ costs about 40 MB as 32-bit integers, and buys you factorisations of twenty-odd steps each.
Mathematicians want a computer to confirm that "every even number greater than 2 is the sum of two primes" holds over an enormous range, which means listing all the primes around 10¹⁸ segment by segment. Allocating an array of length 10¹⁸ is out of the question.
Why this fitsA segmented sieve only needs the primes up to √R (below 10⁹), and then crosses off their multiples inside a window [L, R] a few million wide, so memory depends only on the size of the window. The verification project run by Oliveira e Silva and others uses exactly this segmented approach, sweeping the whole range one segment at a time.
Reach for it when you see:You need every prime below some limit, many primality queries, many prime factorisations (the smallest-prime-factor table), the primes inside a range [L, R], or a limit around 10⁷ where an array still fits in memory.
02The core idea
The most direct way to test whether a number is prime is trial division up to √x, but listing every prime below N one number at a time costs O(N√N). The sieve of Eratosthenes turns the problem around: instead of examining each number, it lets each prime cross off its own multiples. Start by treating everything from 2 to N as possibly prime and scan upwards. The first number p that has not been crossed off must be prime, because a prime factor smaller than itself would have crossed it off already. Cross off all the multiples of p, then move on to the next survivor.
Two observations make it fast. First, the multiples of p only need crossing off from p² onwards: a smaller multiple is p·k with k < p, and since k's prime factors are smaller than p, that number was already crossed off while the smaller prime was being handled. Second, you can stop once p² > N: every composite not exceeding N can be written as a·b with a ≤ b, so a² ≤ N, which means it has a prime factor no larger than √N and was crossed off long ago. The outer loop therefore only runs to √N, and everything still standing in the array afterwards is prime.
Complexity: a prime p crosses off roughly N/p entries, for a total of N/2 + N/3 + N/5 + N/7 + …, and the sum of the reciprocals of the primes grows only as fast as log log N, so the time is O(N log log N). At N = 10⁷, ln ln N is still under 3, which makes it practically linear. Space is a single boolean array of length N + 1, O(N). Two common variants: the linear sieve crosses off each composite exactly once, by its smallest prime factor, in strict O(N), and hands you a smallest-prime-factor table as a bonus, after which any x ≤ N factorises in O(log x); the segmented sieve first computes the primes up to √R and uses them to cross off multiples inside a window [L, R], so even an R as large as 10¹² needs only enough memory for √R plus the window.
Common pitfalls: forgetting to mark 0 and 1 as non-prime; allocating an array of N instead of N + 1; in C++, p * p overflowing once N approaches 2³¹, which is why it is written p <= n / p; crossing off from 2p, which is correct but wastes a lot of steps on numbers already crossed off; and the segmented sieve's starting point, which has to be the larger of p² and the first multiple of p inside the window, or a small L will cross off p itself. How this fits with the neighbouring lessons: the previous one, GCD, needs no factorisation at all, and the sieve is precisely the tool for factorising in bulk; the next one, Modular Arithmetic, usually takes a prime as its modulus, and Fermat's little theorem requires one. If all you need is to test whether a single number around 10¹⁸ is prime, reach for a probabilistic test like Miller–Rabin rather than a sieve.
03The algorithm
- 1Allocate a boolean array
is_primeof lengthN + 1, set every entry to true, then set 0 and 1 to false. - 2Walk p upwards from 2, continuing as long as
p² ≤ N. - 3If
is_prime[p]is still true, p is prime: setp², p² + p, p² + 2p, …to false at every position up to N. Otherwise move straight on to the next p. - 4Stop once
p² > N. Every position still true is a prime not exceeding N. - 5For bulk factorisation, switch to a linear sieve that records the smallest prime factor. When the limit is too large for an array, sieve only up to
√Rand run a segmented sieve over[L, R].
04Interactive demo
1 through 60, ten per row, with √60 ≈ 7.75. Blue is the prime p just confirmed, yellow are the multiples crossed off in this step, a yellow dashed cell is a number a smaller prime had already crossed off that this round visits again, grey with a strikethrough is composite, and green is a confirmed prime. p = 2 starts at 4 and crosses off all 29 even numbers; p = 3 starts at 9, since its smaller multiple 6 was already taken by 2, visiting 18 numbers and crossing off 9 new ones; p = 5 starts at 25 and adds only 25, 35 and 55; p = 7 adds nothing but 49. The next number left standing is 11, but 11² = 121 > 60, so the sieve stops. The table underneath records how much work each prime did: 57 visits in total and 42 composites crossed off, 15 of those crossed off more than once, leaving the 17 primes below 60.
| p | Start p² | Visits | Newly crossed |
|---|---|---|---|
| Nothing crossed out yet | |||
05Code
Python has the standard sieve (a slice crosses off a whole run of multiples at once), plus the linear sieve that records smallest prime factors and the table lookup that factorises with it. C++ has the plain sieve and a segmented one, demonstrated by finding the primes between 10¹² and 10¹² + 100: it sieves only up to √R = 10⁶, and the array is a mere 101 entries long.
def sieve(n):
"""Sieve of Eratosthenes: is_prime[x] is True when x is prime. O(n log log n)"""
is_prime = [True] * (n + 1)
is_prime[0:2] = [False] * min(2, n + 1) # neither 0 nor 1 is prime
p = 2
while p * p <= n: # stop once p² > n: a larger p has no multiples left to cross off
if is_prime[p]:
# start at p²: smaller multiples p·k (k < p) were already crossed off by k's prime factors
is_prime[p * p::p] = [False] * ((n - p * p) // p + 1)
p += 1
return is_prime
def linear_sieve(n):
"""Linear sieve: every composite is crossed off once, by its smallest prime factor. Returns (primes, spf). O(n)"""
spf = [0] * (n + 1) # spf[x]: the smallest prime factor of x
primes = []
for i in range(2, n + 1):
if spf[i] == 0: # nothing crossed it off, so it is prime
spf[i] = i
primes.append(i)
for p in primes:
if p > spf[i] or i * p > n: # once p passes i's smallest prime factor, p is no longer the smallest factor of i·p
break
spf[i * p] = p
return primes, spf
def factorize(x, spf):
"""Factorise through the smallest-prime-factor table. Every step divides by at least 2, so O(log x)"""
factors = []
while x > 1:
p, cnt = spf[x], 0
while x % p == 0:
x //= p
cnt += 1
factors.append((p, cnt))
return factors
if __name__ == "__main__":
is_prime = sieve(60)
print([x for x in range(61) if is_prime[x]])
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
print(sum(sieve(10**6))) # 78498: how many primes there are below one million
primes, spf = linear_sieve(100)
print(len(primes), factorize(84, spf), factorize(97, spf))
# 25 [(2, 2), (3, 1), (7, 1)] [(97, 1)]06Practice
- LeetCode 204Count PrimesMedium
- LeetCode 2523Closest Prime Numbers in RangeMedium
- LeetCode 2521Distinct Prime Factors of Product of Array (factorise with the smallest-prime-factor table)Medium
- LeetCode 3233Find the Count of Numbers Which Are Not Special (only the square of a prime has exactly two proper divisors)Medium
- LeetCode 952Largest Component Size by Common Factor (factorise, then merge with union-find)Hard
- LeetCode 2709Greatest Common Divisor TraversalHard