Problem: Write a C Program to find LCM of n numbers or array of n numbers.

Recommended: LCM of two numbers in C

LCM (Least Common Multiple) of any two numbers is the minimum positive integer that is divisible by both the numbers.

Example: LCM of 5 and 6 is 30.

Similarly, LCM of n numbers is the minimum positive integer that is divisible by all the n numbers.

Example: LCM of 2, 4 and, 8 is 8.

To find LCM of n numbers we will use the concept of GCD.

For any 2 numbers the following relation holds true:

LCM = (n1*n2)/GCD.

But this is not valid for more than 2 numbers i.e. 

LCM != (n1*n2*n3)/GCD.

Thus to find lcm of the whole array we will have to deal with two numbers at a time and use its result for the succeeding number.

Suppose LCM of the first two numbers of the array (i.e. array[0] and array[1]) is lcm1, for next iteration we will find the LCM of lcm1 and array[2] as lcm2, then for 3rd iteration, the LCM of lcm2 and array[3] would be lcm3 and so on.

The last LCM value i.e. the LCM of lcm(n-1) and arra[n] would be the LCM of the whole array.

Overall, we will loop through the array and use Lcm of the last n-1 numbers * array[n] / GCD of the last n numbers to find the lcm of the whole array.

Here is the implementation of the above algorithm in C.

Output

In this tutorial, we learned to find LCM of n numbers in C programming language.

Leave a Reply