Hello Everyone,
LCM (Least Common Multiple) of two numbers is the smallest number which can be divided by both numbers.
For example, LCM of 15 and 20 is 60, and LCM of 5 and 7 is 35.
An efficient solution is based on the below formula for LCM of two numbers ‘a’ and ‘b’.
a x b = LCM(a, b) * GCD (a, b) LCM(a, b) = (a x b) / GCD(a, b)
Below is the implementation of the above idea:
// C++ program to find LCM of two numbers
#include <iostream>
using namespace std;
// Recursive function to return gcd of a and b
long long gcd( long long int a, long long int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to return LCM of two numbers
long long lcm( int a, int b)
{
return (a / gcd(a, b)) * b;
}
// Driver program to test above function
int main()
{
int a = 15, b = 20;
cout << "LCM of " << a << " and "
<< b << " is " << lcm(a, b);
return 0;
}
Output
LCM of 15 and 20 is 60
Note:
In arithmetic and number theory, the least common multiple , lowest common multiple , or smallest common multiple of two integers a and b , usually denoted by lcm( a , b ) , is the smallest positive integer that is divisible by both a and b Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero. However, some authors define lcm( a ,0) as 0 for all a , which is the result of taking the lcm to be the least upper bound in the lattice of divisibility.
The lcm is the “lowest common denominator” (lcd) that can be used before fractions can be added, subtracted or compared. The lcm of more than two integers is also well-defined: it is the smallest positive integer that is divisible by each of them.
A multiple of a number is the product of that number and an integer. For example, 10 is a multiple of 5 because 5 × 2 = 10, so 10 is divisible by 5 and 2. Because 10 is the smallest positive integer that is divisible by both 5 and 2, it is the least common multiple of 5 and 2. By the same principle, 10 is the least common multiple of −5 and −2 as well.
The least common multiple of two integers a and b is denoted as lcm( a , b ). Some older textbooks use [ a , b ], uses a*.b .
Example:
{lcm} (4,6)
Multiples of 4 are:
4,8,12,16,20,24,28,32,36,40,44,48,52,56,60,64,68,72,76,…
Multiples of 6 are:
6,12,18,24,30,36,42,48,54,60,66,72,…
Common multiples of 4 and 6 are the numbers that are in both lists:
12,24,36,48,60,72,…
In this list, the smallest number is 12. Hence, the least common multiple is 12.