Least Common Multiple (LCM) of two numbers is the smallest number which can be divided by both numbers. or The smallest positive number that is a multiple of two or more numbers.
Let’s start with an Example …
List the multiples of each number,
Least Common Multiple (LCM) of 15 and 20:
The multiples of 15 are 15, 30, 45, 60<, 75, 90, … etc
The multiples of 20 are 20, 40, 60, 80, 100, … etc
Find the first Common (same) value:
LCM of 15 and 20 is 60
For example LCM of 15 and 20 is 60 and LCM of 5 and 7 is 35.
LCM of two numbers ‘x’ and ‘y’ can be calculated using following formula.
x * y = LCM(x, y) * GCD (x, y)
LCM(x, y) = (x * y) / GCD(x, y)
The above relation only holds for two numbers,
LCM(x, y, z) != (x * y * z) / GCD( x, y, z)
The main steps of our algorithm are:
Initialize ans = arr[0].
Iterate over all the elements of the array i.e. from i = 1 to i = n-1
At the ith iteration ans = LCM(arr[0], arr[1], …….., arr[i-1]). This can be done easily as LCM(arr[0], arr[1], …., arr[i]) = LCM(ans, arr[i]). Thus at i’th iteration we just have to do ans = LCM(ans, arr[i]) = ans x arr[i] / gcd(ans, arr[i])
Below is a implementation in java of above algorithm:
// Java program to find LCM of array elements
public class TestLCM {
// function to find GCD of 'x' and 'y'
int gcd(int x, int y) {
if (y == 0) {
return x;
}
return gcd(y, x % y);
}
// Returns LCM of array elements
int lcm(int arr[], int n) {
// Initialize result
int 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;
}
//driver method
public static void main(String[] args) {
TestLCM t1 = new TestLCM();
int a[] = {1, 5, 7, 4, 8};
System.out.println("LCM is " + t1.lcm(a, a.length));
int b[] = {3, 5, 7, 9, 34, 12};
System.out.println("LCM is:" + t1.lcm(b, b.length));
}
}
output:
run:
LCM is 280
LCM is:21420
BUILD SUCCESSFUL (total time: 0 seconds)
hellotech 