The least common multiple can be computed by using the greatest common divisor (or GCD) of a and b,
a b | |
LCM(a, b) = | |
GCD(a, b) |
Thus, Euclid's algorithm for GCD gives us a fast algorithm for LCM. As an example, the LCM of 12 and 15 is 12 * 15 / 3 = 60.