Least Common Multiple

The LCM of two numbers is the smallest positive integer that both divide. Thanks to GCD, computing LCM is a one-liner.

LCM from GCD

The relationship is simple:

LCM(a, b) = a / GCD(a, b) * b

Divide first to avoid overflow: (a / gcd) × b stays smaller than a × b / gcd.

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

fn lcm(a: u64, b: u64) -> u64 {
    a / gcd(a, b) * b
}

⚠️ Watch for overflow

For numbers up to 10⁹, a × b can overflow a 32-bit int. Always use long long (C++) or u64 (Rust) for LCM.

Compute LCM across multiple numbers by folding: LCM(a, b, c) = LCM(LCM(a, b), c).

long long result = 1;
for (int x : arr) {
    result = lcm(result, x);
}

let result = arr.iter().fold(1, |acc, &x| lcm(acc, x));