What is the most efficient way to calculate the least common multiple of two integers?
MathMath Problem Overview
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 );
Math Solutions
Solution 1 - Math
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 - Math
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 - Math
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 - Math
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 - Math
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;
Solution 6 - Math
I don't know whether it is optimized or not, but probably the easiest one:
public void lcm(int a, int b)
{
if (a > b)
{
min = b;
max = a;
}
else
{
min = a;
max = b;
}
for (i = 1; i < max; i++)
{
if ((min*i)%max == 0)
{
res = min*i;
break;
}
}
Console.Write("{0}", res);
}
Solution 7 - Math
Here is a highly efficient approach to find the LCM of two numbers in python.
def gcd(a, b):
if min(a, b) == 0:
return max(a, b)
a_1 = max(a, b) % min(a, b)
return gcd(a_1, min(a, b))
def lcm(a, b):
return (a * b) // gcd(a, b)
Solution 8 - Math
Using Euclidean algorithm to find gcd and then calculating the lcm dividing a by the product of gcd and b worked for me.
int euclidgcd(int a, int b){
if(b==0)
return a;
int a_rem = a % b;
return euclidgcd(b, a_rem);
}
long long lcm(int a, int b) {
int gcd=euclidgcd(a, b);
return (a/gcd*b);
}
int main() {
int a, b;
std::cin >> a >> b;
std::cout << lcm(a, b) << std::endl;
return 0;
}
Solution 9 - Math
Take successive multiples of the larger of the two numbers until the result is a multiple of the smaller.
this might work..
public int LCM(int x, int y)
{
int larger = x>y? x: y,
smaller = x>y? y: x,
candidate = larger ;
while (candidate % smaller != 0) candidate += larger ;
return candidate;
}
Solution 10 - Math
C++ template. Compile time
#include <iostream>
const int lhs = 8, rhs = 12;
template<int n, int mod_lhs=n % lhs, int mod_rhs=n % rhs> struct calc {
calc() { }
};
template<int n> struct calc<n, 0, 0> {
calc() { std::cout << n << std::endl; }
};
template<int n, int mod_rhs> struct calc<n, 0, mod_rhs> {
calc() { }
};
template<int n, int mod_lhs> struct calc <n, mod_lhs, 0> {
calc() { }
};
template<int n> struct lcm {
lcm() {
lcm<n-1>();
calc<n>();
}
};
template<> struct lcm<0> {
lcm() {}
};
int main() {
lcm<lhs * rhs>();
}
Solution 11 - Math
Product of 2 numbers is equal to LCM * GCD or HCF. So best way to find LCM is to find GCD and divide the product with GCD. That is, LCM(a,b) = (a*b)/GCD(a,b).
Solution 12 - Math
Euclidean GCD code snippet
int findGCD(int a, int b) {
if(a < 0 || b < 0)
return -1;
if (a == 0)
return b;
else if (b == 0)
return a;
else
return findGCD(b, a % b);
}
Solution 13 - Math
Extending @John D. Cook answer that is also marked answer for this question. ( https://stackoverflow.com/a/3154503/13272795), I am sharing algorithm to find LCM of n numbers, it maybe LCM of 2 numbers or any numbers. Source for this code is this
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Returns LCM of array elements
ll findlcm(int arr[], int n)
{
// Initialize result
ll ans = arr[0];
// ans contains LCM of arr[0], ..arr[i]
// after i'th iteration,
for (int i = 1; i < n; i++)
ans = arr[i] * ans/gcd(arr[i], ans);
return ans;
}
Solution 14 - Math
First calculate GCD using efficacy ways then get lcm from gcd using this formula
lcm = (n1 * n2) / gcd;
For calculation for GCD we use this logic
for (int i = 1; i <= n1 && i <= n2; ++i) {
if (n1 % i == 0 && n2 % i == 0)
gcd = i;
}
We can calculate LCM using recursion also . This is java example for find lcm using gcd .
public class LCMUsingGCD {
public static void main(String[] args) {
int n1 = 40, n2 = 50, gcd = 1;
for (int i = 1; i <= n1 && i <= n2; ++i) {
if (n1 % i == 0 && n2 % i == 0)
gcd = i;
}
int lcm = (n1 * n2) / gcd;
System.out.println("LCM :" + lcm + " of n1 : " + n1 + " and n2 : "
+ n2);
}
}
Solution 15 - Math
Since we know the mathematic property which states that "product of LCM and HCF of any two numbers is equal to the product of the two numbers".
lets say X and Y are two integers, then X * Y = HCF(X, Y) * LCM(X, Y)
Now we can find LCM by knowing the HCF, which we can find through Euclidean Algorithm.
LCM(X, Y) = (X * Y) / HCF(X, Y)
Hope this will be efficient.
import java.util.*;
public class Hello {
public static int HCF(int X, int Y){
if(X == 0)return Y;
return HCF(Y%X, X);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int X = scanner.nextInt(), Y = scanner.nextInt();
System.out.print((X * Y) / HCF(X, Y));
}
}
Solution 16 - Math
Yes, there are numerous way to calculate LCM such as using GCD (HCF). You can apply prime decomposition such as (optimized/naive) Sieve Eratosthenes or find factor of prime number to compute GCD, which is way more faster than calculate LCM directly. Then as all said above, LCM(X, Y) = (X * Y) / GCD(X, Y)
Solution 17 - Math
There is no way more efficient than using a built-in function!
As of Python 3.8 lcm() function has been added in math library. And can be called with folowing signature:
math.lcm(*integers)
Returns the least common multiple of the specified integer arguments. If all arguments are nonzero, then the returned value is the smallest positive integer that is a multiple of all arguments. If any of the arguments is zero, then the returned value is 0. lcm() without arguments returns 1.