Euclidean Algorithm

Knowledge Summary

Greatest Common Divisor (GCD)

The greatest common divisor of two integers is the largest positive integer that divides both of them.

Euclidean Algorithm

Core idea: gcd(a, b) = gcd(b, a % b). Continue until b = 0, then a is the result.

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

Example: gcd(48, 18)

• gcd(48, 18) -> gcd(18, 12) -> gcd(12, 6) -> gcd(6, 0) = 6

Least Common Multiple (LCM)

lcm(a, b) = a × b / gcd(a, b)

int lcm(int a, int b) {
    return a / gcd(a, b) * b; // divide first, then multiply to avoid overflow
}

Related Properties

• gcd(a, 0) = a
• gcd(a, 1) = 1
• If gcd(a, b) = 1, then a and b are coprime
• gcd(a, b) × lcm(a, b) = a × b

Built-in C++ Functions

Since C++17, you can directly use __gcd(a, b) or gcd(a, b) from <numeric>.