Sieve of Eratosthenes
Math & Number Theory: lesson 3 of 5
Cross out what the primes can reach; the rest are prime.
Lesson 3 of 5 · 5 min
Sieve of Eratosthenes
Step 1 of 8
Thirty numbers. Testing each one for divisors means thousands of divisions — so test none of them.
The Idea
Do not test numbers for primality. Cross out what you already know is composite.
Take the smallest number nothing has struck: it is prime, because no smaller value divides it. Strike its multiples, starting at its square, and move on. Whatever survives is prime by construction, at a cost near n log log n instead of n divisions each.
Real-World Example
Project Euler-style workloads, competitive programming and anything needing "all primes below a million" build the table once and answer every later question by lookup. Cryptographic libraries do the opposite of this at a much larger scale, sieving small factors away before running an expensive probabilistic test.
The Code
def primes_up_to(n):
ok = [True] * (n + 1)
ok[0] = ok[1] = False
for p in range(2, int(n ** 0.5) + 1):
if ok[p]: # p survived, so p is prime
for k in range(p * p, n + 1, p): # below p*p, someone else struck it
ok[k] = False
return [i for i, good in enumerate(ok) if good]
print(primes_up_to(31)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
print(len(primes_up_to(100))) # 25Your turn
Put the steps in the right order.
- Take the smallest number still unmarked — it is prime
- Mark every number as a candidate
- Stop once the square of the candidate passes n; everything unmarked is prime
- Cross out its multiples, starting at its square
Mini quiz
1 / 3