C Program to Find LCM of n Numbers

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.

#include <stdio.h>
int findGCD(int, int);

int main() {
    int array[] = {8, 4, 2, 16};
    int lcm = array[0];;
    int  gcd = array[0];
 
    //Loop through the array and find GCD
    //use GCD to find the LCM
    for(int i=1; i<4; i++){
      gcd = findGCD(array[i], lcm);
      lcm = (lcm*array[i])/gcd;
    }
    
    printf("LCM: %d", lcm);
}

//Function returns GCD of a and b
int findGCD(int a, int b){
    if(b==0)
        return a;
    return findGCD(b, a%b);
}

Output

LCM: 16

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