C Program to Compute LCM of Multiple Integers

In mathematics, Least Common Multiple or Lowest Common Multiple (LCM) of two integers is the lowest possible positive integer that is divisible by both the integers. We’ll first see how to write C program to compute LCM of two integers. Then we’ll extend that logic for multiple integers.

APPROACH 1: LCM Using GCD

We can compute the LCM of two numbers using the theory that the multiplication of two numbers is equal to the multiplication of their LCM and GCD. For that we have to first compute their multiplication (say M) and their GCD (say G). Then their LCM would be M / G.

Here is the program.

#include <stdio.h>

int gcd(int a, int b)
{
  if (b == 0) return a;
 
  return gcd(b, a % b);
}

int lcm(int a, int b)
{
  return (a*b / gcd(a, b));
}

void main()
{
  int a, b, result;

  printf("Enter the two numbers to find their LCM: ");
  scanf("%d%d", &a, &b);

  result = lcm(a, b);
  printf("The LCM of %d and %d is %d.\n", a, b, result);
}

This program takes input of two integers and calls the lcm() function to compute their LCM.

Here is the output of the above program.

APPROACH 2: LCM WITHOUT GCD

We can compute LCM without GCD also. We can increment a number, starting from 1, in a loop until the number becomes divisible by both the input numbers.

Here is the program.

#include <stdio.h>

int lcm(int a, int b)
{
    int m = 1;

    while(m%a || m%b) m++;

    return m;
}

void main()
{
 int a, b, result;

  printf("Enter the two numbers to find their LCM: ");
  scanf("%d%d", &a, &b);

  result = lcm(a, b);
  printf("The LCM of %d and %d is %d.\n", a, b, result);
}

Compute LCM of Multiple Integers

We can compute LCM of multiple integers using the above lcm() function.

#include <stdio.h>

int lcm(int a, int b)
{
    int m = 1;

    while(m%a || m%b) m++;

    return m;
}

void main()
{
  int arr[] = {15, 35, 55, 555, 65, 945, 25, 875, 45};
  int result, size, i;

  size = sizeof(arr) / sizeof(int);
  result = arr[0];

  for (i = 1; i < size; i++)
  {
    result = lcm(result, arr[i]);
  }

  printf("The LCM of the array is %d.\n", result);
}

First we assumed that first element of the array is the LCM (set as result). Then we called the lcm() function with the result and the second element. The return value is set to result. Then we call the lcm() function again with the result and the third element. We continued the same thing for rest of the array elements. The final result will become the LCM for all elements of the array.

This approach is very inefficient in terms of computation time. We can write a function that will take the whole array as input and compute the LCM in one go.

#include <stdio.h>

int lcm(int *arr, int size)
{
    int i =0;
    int m = arr[0];

    while (1) {
      
      for (i = 0; i < size; i++) {
        if(m % arr[i]) break;
      }
      if( i == size) break;
      m++;
    }

    return m;
}

void main()
{
  int arr[] = {15, 35, 55, 555, 65, 945, 25, 875, 45};
  
  int result, size;

  size = sizeof(arr) / sizeof(int);
  result = lcm(arr, size);

  printf("The LCM of the array is %d.\n", result);
}

This program is much efficient than the previous one.

If you also want to contribute, click here.