Menu
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 ); 
602
Therefore, the formula to find LCM of two numbers is, LCM of two numbers = product of two numbers ÷ HCF of two numbers. Note: The LCM of two co-prime numbers is equal to the product of co-prime numbers because the highest common factor of prime numbers is 1.
Prime Factorization Method of Finding LCMStep 1: To first list the prime factors of each number. Step 2: Next multiply each factor the maximum number of times it occurs in either number. If the same factor occurs more than once in both numbers, then multiply the factor the maximum number of times it occurs.
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.
137
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
