Number theory is the math of whole numbers — primes, divisibility, and remainders. A handful of small algorithms cover almost everything you need in interviews and competitive programming. The headline one is the Sieve of Eratosthenes: a beautifully simple way to find every prime up to some limit, far faster than testing each number on its own.
The core idea. A prime has no factors except 1 and itself. So instead of checking each number, flip it around: take each prime in turn and cross out all of its multiples. Anything never crossed out must be prime.
Intuition
Imagine a list of numbers from 2 to 30 written on a chalkboard. You circle 2 (the first prime), then walk down the board erasing every second number after it — 4, 6, 8, and so on. The next number still standing is 3, so you circle it and erase every third number. Then 5. You only ever have to do this for primes up to √30, because any composite number has a factor no larger than its square root. Whatever survives the erasing is prime. That is the whole sieve.
Walk through it
Step through the animation on the right. The numbers 2 to 30 start as plain cells. When a number is the next one still standing, it turns green — that means it is prime. Then we sweep through its multiples and dim them out (they are composite, removed from the running). Notice each sweep starts at p × p, not 2p: every smaller multiple already got crossed out by a smaller prime, so starting earlier would just repeat work.
Watch the pattern: 2 wipes out all the evens, 3 wipes out 9, 15, 21, 27, and 5 only needs to touch 25 and 30. By the time we finish 5, every remaining number — 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — is prime.
The code, line by line
def sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for p in range(2, int(n**0.5) + 1):
if is_prime[p]:
for m in range(p * p, n + 1, p):
is_prime[m] = False
return [i for i in range(2, n + 1)
if is_prime[i]]- Line 2 makes a boolean array where every index is assumed prime to begin with.
- Line 3 marks 0 and 1 as not prime — they are special cases that the loop never visits.
- Line 4 loops only up to
√n. Any compositechas a factor≤ √c ≤ √n, so a largerpcan never be the smallest factor of an uncrossed number. - Line 5 skips numbers already crossed out — if
pis composite, all its multiples were handled byp's own prime factors. - Lines 6 to 7 are the heart: cross out
p × p, p × p + p, …up ton. - Lines 8 to 9 collect every index still marked prime.
Two more must-know tools
GCD with Euclid. The greatest common divisor of a and b is found by repeatedly replacing the pair with (b, a % b) until the second is 0:
def gcd(a, b):
while b:
a, b = b, a % b
return aIt works because any common divisor of a and b also divides a % b. This runs in O(log min(a, b)) — astonishingly fast.
Modular exponentiation (fast power). To compute a**b mod m for huge exponents without overflow, use repeated squaring. Python has it built in: pow(a, b, m) does exactly this in O(log b) multiplications. Reach for it whenever you see "modulo a large prime" — for example computing combinations mod 10**9 + 7.
Complexity
| Case | Time | Notes |
|---|---|---|
| Sieve to n | O(n log log n) (moderate) | near-linear — each prime crosses out n/p numbers |
| Trial-divide each number | O(n √n) (moderate) | far slower for large n |
| Euclid GCD | O(log min(a, b)) (moderate) | remainder shrinks fast |
| Fast power pow(a, b, m) | O(log b) (moderate) | repeated squaring |
O(n) (moderate)Why O(n log log n) for the sieve? For each prime p we touch about n / p numbers, and summing 1/p over all primes up to n grows like log log n — almost a constant. The space is O(n) for the boolean array.
When to use / pitfalls
Use the sieve when you need many primes or repeated primality checks up to a fixed limit — it
precomputes them all in one near-linear pass. For a single "is this one number prime" check on a huge
number, trial division up to √n (or a probabilistic test) is simpler. Know Euclid's GCD and pow(a, b, m)
cold — they show up constantly.
Two classic off-by-one traps. First, the inner loop must start at p * p, not 2 * p — starting later
is what makes the sieve fast. Second, remember to mark 0 and 1 as not prime; forgetting this is the
most common bug, since 1 has exactly one divisor and is not prime by definition.
Practice
When the sieve processes the prime 5 for n = 30, which numbers does its inner loop cross out?
1. Why does the outer loop only run while p is at most √n?
2. Why does the inner loop start at p * p instead of 2 * p?
3. What is the time complexity of the Sieve of Eratosthenes?
4. What does Euclid's algorithm gcd(a, b) replace the pair with each step?