What is the most efficient way to calculate the least common multiple of two integers?

The least common multiple (lcm) of a and b is their product divided by their greatest common divisor (gcd) ( i.e. lcm(a, b) = ab/gcd(a,b)).

So, the question becomes, how to find the gcd? The Euclidean algorithm is generally how the gcd is computed. The direct implementation of the classic algorithm is efficient, but there are variations that take advantage of binary arithmetic to do a little better. See Knuth's "The Art of Computer Programming" Volume 2, "Seminumerical Algorithms" § 4.5.2.

Remember The least common multiple is the least whole number that is a multiple of each of two or more numbers.

If you are trying to figure out the LCM of three integers, follow these steps:

  **Find the LCM of 19, 21, and 42.**

Write the prime factorization for each number. 19 is a prime number. You do not need to factor 19.

21 = 3 × 7
42 = 2 × 3 × 7
19

Repeat each prime factor the greatest number of times it appears in any of the prime factorizations above.

2 × 3 × 7 × 19 = 798

The least common multiple of 21, 42, and 19 is 798.

I think that the approach of "reduction by the greatest common divider" should be faster. Start by calculating the GCD (e.g. using Euclid's algorithm), then divide the product of the two numbers by the GCD.