Skills101

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, ….

Sieve of Eratosthenes up to 60 in a grid of 10 columns: the 17 primes are green, and the other numbers are coloured by the first prime that crossed them out, 2, 3, 5 or 7

Two details make it fast:

  • Start crossing at p × p. Smaller multiples like 3p were already crossed out by the smaller prime 3.
  • Only primes p ≤ √N need 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.

OperationSafe form
Addition(a + b) % M
Multiplication(a * b) % M — use long in Java
Subtraction((a − b) % M + M) % M — avoid negatives
Divisionmultiply 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.

Fast power table for 3 to the power 13 mod 1000: 13 is 1101 in binary; four loop steps multiply the result by the base when the bit is 1 and square the base every time, giving 323

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 − 1 instead 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 with int, which can overflow before the division. Divide first: a / gcd * b, using long.
  • Taking % M only at the end, after the value has already overflowed.
  • Writing (a − b) % M in 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).

Practice what you learned

📝 Quiz: Number Theory for Coding5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →