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

Question

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

I just came up with this, but it definitely leaves something to be desired.

int n=7, m=4, n1=n, m1=m;

while( m1 != n1 ){
    if( m1 > n1 )
        n1 += n;
    else 
        m1 += m;
}

System.out.println( "lcm is " + m1 );

Answer 1

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.