Math & Number Theory
01 / The shared mechanism
Many problems hide a number-theoretic backbone. Once you recognize the divisibility / modular / multiplicative structure the input really has, an O(N) loop collapses to O(log N) or O(N log log N). Three classic sub-patterns: gcd by Euclidean reduction, modular power by exponent-bit doubling, prime sieve by marking multiples once.
01 / The one-sentence essence
Walk the multiples of every prime in one shared pass. Composites get marked by their smallest prime factor first; primes survive to mark their own multiples. The whole table fills itself in O(N log log N) — each composite is touched O(log log N) times amortized, not once per divisor.
Problemfind all primes up to NN20
Assume every number from 2 to 20 is prime. We'll mark composites by walking the multiples of each surviving prime.
step
0 / 16
prime
—
primes
—
N
20
0 / 16
02 / The pattern signature
# Sieve of Eratosthenesis_prime[0..N] ← [True] * (N+1)is_prime[0] = is_prime[1] ← Falsefor p in 2..⌊√N⌋:if is_prime[p]:for m in p*p..N step p: # start at p² — smaller multiples already markedis_prime[m] ← Falsereturn [i for i in 2..N if is_prime[i]]
03 / When to recognize this pattern
"all primes up to N"
The canonical use — LC 204. Beats trial-divide-each-number by a log factor; beats Wilson's theorem by every factor you can name. If your
N fits in memory, this is the answer."smallest prime factor of each number"
The linear-sieve variant: while scanning, the first prime to mark
m composite is its smallest prime factor. Store it in spf[m] instead of just a boolean — now any number factors in O(log m)."factorization of many numbers"
Precompute
spf[] once in O(N log log N), then factor each query in O(log n) by repeatedly dividing by spf[n]. Q queries on values up to N: O(N log log N + Q log N) total."sum / count of primes with property"
When the question reduces to "iterate over primes ≤ N" — count primes, sum of prime-indexed values, primes p with p mod k = r. Sieve once, then filter. Don't trial-divide each candidate independently.
04 / Common pitfalls
i.
Starting the inner loop at
p*2 instead of p*p.Wastes work — every multiple of
p below p*p has a smaller prime factor and has already been marked. For p = 7, you'd redundantly re-mark 14, 21, 28, 35, 42; only from 49 onward does p contribute new marks. The optimization is what gives the bound its tightness.ii.
Treating the sieve as
O(N log N) instead of O(N log log N).The naive bound
Σ N/p over primes p ≤ N looks harmonic-like — but prime reciprocals sum to log log N + O(1) (Mertens' theorem), not log N. Cite the right bound: it's tighter than N log N by a meaningful margin at the scales you actually run.iii.
Off-by-one in the upper bound for
p.The outer loop should run
p up to and including ⌊√N⌋ — not strictly less. Any composite m ≤ N has a prime factor ≤ √m ≤ √N, so primes above √N never contribute new marks, but p = √N itself does when N is a perfect square.05 / Go practice — on LeetCode
Four problems. First is the textbook sieve; the others are downstream uses of the same precomputed prime / SPF table — factorization, multiplicative counting, GCD-based grouping.
— / When to use which
gcd / lcm
Use whenever divisibility is the heart of the problem — common factor, coprimality test, simplest fraction, LCM via
a · b / gcd(a, b). Euclid's identity gcd(a, b) = gcd(b, a % b) drops each step geometrically.Euclidean · LC 1071 · LC 1979
modular power
Use whenever you need
aⁿ mod M for huge n, or a multiplicative inverse mod a prime. Halve the exponent each step; the bit pattern of n picks which squarings contribute. O(log n) instead of O(n).exponent halving · LC 50 · LC 372
prime sieve
Use when you need all primes up to N (or all smallest prime factors). For each prime p walk its multiples and mark them composite — every composite is marked O(log log N) times amortized.
Eratosthenes · LC 204 · LC 952