Lesson 17 — Count primes

The sieve of Eratosthenes

A prime is a number above 1 divisible only by 1 and itself (2, 3, 5, 7…). Testing each number separately is slow. The sieve is faster: make a list of True flags, then for every prime p, cross out (set False) all its multiples starting at p × p. Whatever stays True is prime.

for m in range(9, 40, 3):   # 9, 12, 15, ... (multiples of 3 from 3*3)
    marks[m] = "x"

Why it matters: precomputing answers for a whole range at once beats checking one by one — and primes are the basis of internet encryption.