Coding rounds love number theory because it is compact and easy to test: greatest common divisors, prime checks and sieves, modular arithmetic, and computing large powers. Each has a standard efficient method worth memorising.
Euclid, sieve, and modular math
Three tools cover most questions: Euclid's algorithm for GCD (and hence LCM), the Sieve of Eratosthenes for all primes up to n, and modular arithmetic (with fast exponentiation) for very large numbers.
Euclid's GCD and the Sieve of Eratosthenes
function gcd(a, b):
while b != 0:
a, b = b, a mod b // remainder shrinks fast
return a
function sieve(n):
isPrime = [true] * (n+1); isPrime[0]=isPrime[1]=false
for p = 2 while p*p <= n:
if isPrime[p]:
for m = p*p to n step p: isPrime[m] = false
return all p with isPrime[p]gcd O(log min(a,b))→sieve O(n log log n)
Euclid shrinks fast; the sieve crosses out multiples.
⚡ The edge
- GCD by Euclid: gcd(a, b) = gcd(b, a mod b) — and LCM(a, b) = a×b / gcd(a, b).
- To test primality you only need divisors up to √n; to compute a^b mod m for huge b, use fast exponentiation (square and multiply) in O(log b).
Worked example
Compute gcd(48, 18) using Euclid's algorithm.
- gcd(48, 18): 48 mod 18 = 12, so gcd(48,18) = gcd(18, 12).
- gcd(18, 12): 18 mod 12 = 6, so = gcd(12, 6); then 12 mod 6 = 0.
- When the remainder hits 0, the previous value (6) is the GCD.
Answer: gcd(48, 18) = 6
Worked example
Why test divisors only up to √n when checking if n is prime?
- If n = a×b with both a and b greater than √n, then a×b would exceed n — impossible.
- So at least one factor of any composite n is ≤ √n.
- Finding no divisor up to √n means n is prime; this cuts the work from O(n) to O(√n).
Answer: Any factor pair has one member ≤ √n, so checking to √n suffices
⚠ Watch out
- Watch for integer overflow when multiplying (a×b for LCM or powers) — take the modulus early.
- The modulo of a negative number is language-dependent; normalise to a non-negative result if needed.
- In the sieve, start crossing out from p×p and remember 0 and 1 are not prime.