AdvancedData Structures & Algorithms · Lesson 38 of 40 · Updated ·
Number Theory for Coding — GCD, Primes, Sieve and Fast Power
Many coding problems hide a little maths: "when do two buses arrive together again?", "how many primes are there below n?", "print the answer modulo 10⁹ + 7". You do not need advanced theory for these — a handful of short algorithms covers most placement and contest questions. This lesson explains each one, why it is fast, and the traps that cause wrong answers.
1. GCD and LCM with Euclid's algorithm
The GCD (greatest common divisor) of two numbers is the largest number that divides both. The LCM (least common multiple) is the smallest number that both divide.
Euclid's algorithm rests on one fact: gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a. Any number that divides a and b also divides a % b (the remainder is a minus a multiple of b), so the common divisors do not change while the numbers shrink quickly.
def gcd(a, b):
steps = []
while b:
steps.append((a, b))
a, b = b, a % b
return a, steps
g, steps = gcd(252, 105)
print(steps, "->", g)
def lcm(a, b):
return a // gcd(a, b)[0] * b # divide first to keep numbers small
print(lcm(12, 18), lcm(4, 6), lcm(7, 5))
[(252, 105), (105, 42), (42, 21)] -> 21
36 12 35
Two buses leave the college gate together, one every 12 minutes and one every 18 minutes. They leave together again after lcm(12, 18) = 36 minutes. Euclid's algorithm takes O(log(min(a, b))) steps, because the numbers at least halve every two steps. Python has math.gcd and math.lcm built in; in Java you usually write the three-line loop yourself.
2. Is n prime?
A prime is a number greater than 1 whose only divisors are 1 and itself. To test n, you only need to try divisors up to √n: if n = a × b and both were larger than √n, the product would be larger than n. So one of them must be ≤ √n.
def is_prime(n):
if n < 2:
return False
d = 2
while d * d <= n: # same as d <= sqrt(n), without floats
if n % d == 0:
return False
d += 1
return True
print([x for x in range(1, 30) if is_prime(x)])
print(is_prime(97), is_prime(1_000_000_007), is_prime(91))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
True True False
This is O(√n) per number: about 31,600 steps for n = 10⁹ + 7. (91 = 7 × 13 is a classic trick question.)
3. The Sieve of Eratosthenes
To find all primes up to N, testing each number separately is wasteful. The sieve starts by assuming every number from 2 is prime, then for each prime p crosses out its multiples p², p² + p, p² + 2p, ….
Two details make it fast:
- Start crossing at
p × p. Smaller multiples like3pwere already crossed out by the smaller prime 3. - Only primes
p ≤ √Nneed to cross anything; after that, every number left is prime.
def sieve(N):
is_p = [True] * (N + 1)
is_p[0] = is_p[1] = False
p = 2
while p * p <= N:
if is_p[p]:
for k in range(p * p, N + 1, p):
is_p[k] = False
p += 1
return [i for i in range(N + 1) if is_p[i]]
print(sieve(60))
print(len(sieve(100)), len(sieve(1_000_000)))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
25 78498
The sieve runs in O(N log log N) time, which is nearly linear. It needs O(N) memory, so it suits N up to about 10⁷ in most judges.
4. Prime factors and divisors
Every number above 1 is a product of primes in exactly one way (for example 360 = 2³ × 3² × 5). To find the factors, divide out each d while it divides, up to √n. Whatever is left above 1 at the end is itself a prime.
Once you have n = p₁^a × p₂^b × …, the number of divisors is (a + 1)(b + 1)…, because each divisor picks a power from 0 to a for p₁, 0 to b for p₂, and so on.
def factorise(n):
f, d = {}, 2
while d * d <= n:
while n % d == 0:
f[d] = f.get(d, 0) + 1
n //= d
d += 1
if n > 1:
f[n] = f.get(n, 0) + 1
return f
for n in [360, 97, 1001]:
f = factorise(n)
count = 1
for e in f.values():
count *= e + 1
print(n, f, "divisors:", count)
360 {2: 3, 3: 2, 5: 1} divisors: 24
97 {97: 1} divisors: 2
1001 {7: 1, 11: 1, 13: 1} divisors: 8
5. Modular arithmetic and 10⁹ + 7
Answers such as "number of paths" grow enormous, so problems ask for the answer modulo M, usually M = 10⁹ + 7. It is a prime, and it is small enough that the product of two values below it fits in a 64-bit integer.
| Operation | Safe form |
|---|---|
| Addition | (a + b) % M |
| Multiplication | (a * b) % M — use long in Java |
| Subtraction | ((a − b) % M + M) % M — avoid negatives |
| Division | multiply by the modular inverse, not / |
Take % M after every step, not only at the end; otherwise Java's long overflows silently. Division is different: (a / b) % M is wrong. Because M is prime, the inverse of b is b^(M − 2) % M (Fermat's little theorem), which needs fast power.
6. Fast power (binary exponentiation)
Computing a^e by multiplying e times takes O(e) — hopeless for e = 10⁹. Fast power uses the binary form of e: square the base at each step, and multiply it into the result whenever the current bit of e is 1.
Since 13 = 8 + 4 + 1, 3¹³ = 3⁸ × 3⁴ × 3¹. The loop runs once per bit: O(log e).
public class Main {
static final long MOD = 1_000_000_007L;
static long power(long base, long e, long mod) {
long result = 1;
base %= mod;
while (e > 0) {
if ((e & 1) == 1) result = result * base % mod; // bit is 1
base = base * base % mod; // square
e >>= 1;
}
return result;
}
static long gcd(long a, long b) {
while (b != 0) { long t = a % b; a = b; b = t; }
return a;
}
public static void main(String[] args) {
System.out.println(power(3, 13, 1000));
System.out.println(power(2, 10, MOD));
System.out.println(power(2, 1_000_000_000L, MOD));
long inv3 = power(3, MOD - 2, MOD); // modular inverse of 3
System.out.println(inv3 + " " + (3 * inv3 % MOD));
System.out.println(gcd(252, 105));
}
}
323
1024
140625001
333333336 1
21
3 × 333333336 % M = 1, so 333333336 acts as "1/3" in modulo arithmetic: to divide by 3, multiply by it. Python's built-in pow(a, e, m) does the same fast power for you.
Common mistakes
- Testing primes up to
n − 1instead of √n, which is far too slow for large n. - Treating 1 as a prime. It is not; the smallest prime is 2.
- Computing
a * b / gcd(a, b)in Java withint, which can overflow before the division. Divide first:a / gcd * b, usinglong. - Taking
% Monly at the end, after the value has already overflowed. - Writing
(a − b) % Min Java or C++ and getting a negative answer. - Dividing under a modulus with
/instead of multiplying by the modular inverse.
Quick recap
gcd(a, b) = gcd(b, a % b);lcm = a / gcd × b; O(log) steps.- Prime test: try divisors up to √n.
- Sieve: cross out multiples of each prime from p², only for p ≤ √N; O(N log log N).
- Divisor count from the prime factorisation: multiply (exponent + 1).
- Under 10⁹ + 7: mod after every step, fix negatives, divide with the inverse
b^(M − 2). - Fast power: square the base, multiply on 1-bits; O(log e).