Lesson 39.1 · Math for Coding Interviews

GCD, LCM and the Sieve

gcd(a, b) = gcd(b, a mod b) runs in O(log min(a, b)). lcm = a / gcd × b. The sieve marks multiples of each prime to find all primes below n in O(n log log n).

14 min

Think of it like this

Tiling a 48 × 18 floor with the largest possible square tiles: cut off 18 × 18 squares until a 12 × 18 strip remains, then 12 × 12 squares, and so on. The last square that fits exactly is the GCD, 6.

1.Euclid and the sieve

GCD: any common divisor of a and b also divides a mod b, so gcd(a, b) = gcd(b, a mod b), ending at gcd(g, 0) = g. LCM: a / gcd(a, b) * b (divide first to avoid overflow).

Sieve of Eratosthenes: assume all numbers ≥ 2 are prime; for each prime p from 2 while p² < n, cross out p², p² + p, … (smaller multiples were already crossed out by smaller primes).

Bézout: the values a·x + b·y (integers x, y) are exactly the multiples of gcd(a, b). That answers water-jug puzzles and "can these step sizes reach a target?".

Main.java

import java.util.*;

public class Main {
    static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }

    public static void main(String[] args) {
        System.out.println("gcd(48, 18) = " + gcd(48, 18));
        System.out.println("lcm(4, 6) = " + (4 / gcd(4, 6) * 6));

        int n = 30;
        boolean[] composite = new boolean[n + 1];
        for (int p = 2; (long) p * p <= n; p++)
            if (!composite[p])
                for (int m = p * p; m <= n; m += p) composite[m] = true;
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) if (!composite[i]) primes.add(i);
        System.out.println("primes up to 30: " + primes);
    }
}

Output

gcd(48, 18) = 6
lcm(4, 6) = 12
primes up to 30: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Remember

Euclid: O(log).
LCM: divide before multiplying.
Sieve from p², while p² ≤ n.

Common mistakes

p * p overflowing int in the sieve loop for large n.
Testing primality by trial division for every number up to n (O(n √n)).

Words used in this lesson

GCD: Greatest common divisor: the largest number dividing both.
Prime: An integer > 1 whose only divisors are 1 and itself.

Command Palette

GCD, LCM and the Sieve

1.Euclid and the sieve