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 );

Solution 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.

Solution 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.

Solution 3:

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.

Solution 4:

Best solution in C++ below without overflowing

#include <iostream>
using namespace std; 
long long gcd(long long int a, long long int b){        
    if(b==0)
        return a;
    return gcd(b,a%b);
}

long long lcm(long long a,long long b){     
    if(a>b)
        return (a/gcd(a,b))*b;
    else
        return (b/gcd(a,b))*a;    
} 

int main()
{
    long long int a ,b ;
    cin>>a>>b;
    cout<<lcm(a,b)<<endl;        
    return 0;
}

Solution 5:

First of all, you have to find the greatest common divisor

for(int i=1; i<=a && i<=b; i++) {

   if (i % a == 0 && i % b == 0)
   {
       gcd = i;
   }

}

After that, using the GCD you can easily find the least common multiple like this

lcm = a / gcd * b;