Eratosthenes and the Linear Sieve
In short: to find every prime up to n, don't test each number on its
own — strike out multiples instead. Starting from each prime p, cross off
p·p, p·p+p, p·p+2p, … up to n; anything never crossed off is prime. That's
the Sieve of Eratosthenes, and it costs O(n log log n). A sharper version,
the linear sieve, strikes every composite exactly once — each composite
is crossed off only by its smallest prime factor — and costs O(n). Quarry's
hash kernel needs this: prime bucket counts, prime moduli and quick
factorisation all start with "which numbers up to n are prime".
Picking a bucket count that resists clustering
Quarry's hash table spreads keys across capacity buckets with
hash(key) % capacity. Pick capacity = 100 and every key that's a multiple
of 10 — user ids 10, 20, 30, … — lands in buckets 0, 20, 40, …: a fifth of
the buckets, used by everything. A prime capacity breaks that pattern,
because a prime shares no common factor with any key except 1.
97 keys hashed into a 97-bucket table land in 97 different buckets, no matter what the key pattern is — because 97 has no factor in common with 10. Pick table sizes from a prime list, not round numbers.
How much faster is striking than testing?
Testing every number up to n for primality, one at a time, costs about
n · √n in the worst case. The sieve strikes multiples instead, and the
total number of strikes is n · Σ(1/p) over primes p ≤ n, which is
n · log log n — a function so slow-growing it's barely above a constant for
any n you'll meet in practice.
n = 100
is_c = [False] * (n + 1)
strikes = 0
p = 2
while p * p <= n:
if not is_c[p]:
m = p * p
while m <= n:
is_c[m] = True
strikes += 1
m += p
p += 1
print(strikes)A live pass over 2..120
Watch three colours of strikes fan out: 2's multiples, then 3's, then 5's and 7's, each starting at the prime's own square because anything smaller was already struck by a smaller prime.
Each prime only strikes from its own square, because smaller primes already cleared everything below it. The circled survivors at the end are every prime up to 120.
The linear sieve: one strike per composite
The classic sieve strikes some composites more than once — 12 gets struck by
both 2 and 3. The linear sieve avoids that by giving every composite
exactly one owner: its smallest prime factor. Walk i from 2 upward. If
i has no owner yet, it's prime. Then, for every prime p found so far
(smallest first), mark p·i as owned by p — but stop as soon as p
exceeds i's own smallest prime factor, because any composite past that
point will get a smaller owner later anyway.
spf[i] falls out for free — it's a byproduct worth keeping. With it,
factorising any number up to n takes O(log n): repeatedly divide by
spf[current].
def spf_ops(n, guard):
spf = [0] * (n + 1)
primes = []
ops = 0
for i in range(2, n + 1):
if spf[i] == 0:
spf[i] = i
primes.append(i)
for p in primes:
if (guard and p > spf[i]) or p * i > n:
break
spf[p * i] = p
ops += 1
return ops
print(spf_ops(2000, True) < spf_ops(2000, False))What it costs
| approach | time | why |
|---|---|---|
| test every number for primality | O(n · √n) | trial division per number |
| Sieve of Eratosthenes (strike from p²) | O(n log log n) | Σ(n/p) over primes ≤ n |
| linear sieve | O(n) | every composite struck exactly once, by its smallest factor |
segmented sieve over [lo, hi] |
O((hi−lo) log log hi + √hi) | sieve the small base primes once, strike only inside the window |
Quick practice
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True
print(is_prime(1), is_prime(2), is_prime(91))This prints `[]` — every number, prime or not, gets struck before it's checked. Reorder so the check-and-append happens first, and strike from `p * p` onward.
🎯 Your turn
Build primes_up_to(n): every prime ≤ n, in order, using the Sieve of
Eratosthenes (strike from p·p, not 2p).
primes_up_to(10)→[2, 3, 5, 7]primes_up_to(30)→[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]primes_up_to(1)→[]
Hint: a boolean array is_composite[0..n]. For each p from 2 up while
p*p <= n, if p isn't marked composite, strike p*p, p*p+p, …. Collect
whatever's left unmarked.
Press ▶ Run, then ✓ Check.