Greatest Common Divisor

Given two positive integers a and b, return their greatest common divisor (GCD): the largest integer that divides both.

Example

Text

Input: 10, 15   Output: 5
Input: 36, 48   Output: 12
Input: 17, 5    Output: 1

Brute force: try every candidate

The GCD cannot be larger than the smaller number. Count down from min(a, b) and return the first value that divides both.

Java

public class Main {
    static long gcd(long a, long b) {
        for (long d = Math.min(a, b); d >= 1; d--) {
            if (a % d == 0 && b % d == 0) return d;
        }
        return 1; // unreachable for positive inputs
    }

    public static void main(String[] args) {
        System.out.println(gcd(10, 15) + " " + gcd(36, 48) + " " + gcd(17, 5));
    }
}

Output

5 12 1

Time: O(min(a, b)). Space: O(1).

Optimal: Euclidean algorithm

Any number that divides both a and b also divides a - b, and therefore a % b. So gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a.

Text

gcd(36, 48) = gcd(48, 36) = gcd(36, 12) = gcd(12, 0) = 12

Java

public class Main {
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    static long lcm(long a, long b) {
        return a / gcd(a, b) * b; // divide first to avoid overflow
    }

    public static void main(String[] args) {
        System.out.println(gcd(10, 15) + " " + gcd(36, 48) + " " + gcd(17, 5));
        System.out.println(lcm(4, 6));
    }
}

Output

5 12 1
12

Time: O(log min(a, b)): the remainder at least halves every two steps. Space: O(1).

The least common multiple follows from gcd(a, b) · lcm(a, b) = a · b.

Edge cases

One number divides the other: the smaller number is the GCD, found after one step.
Zero: gcd(a, 0) = a; the loop handles it without a special case.
Coprime numbers: the GCD is 1.