Finding LCM of more than two (or array) numbers without using GCD

Hello Everyone,

Given an array of positive integers, find LCM of the elements present in array.
Examples:

Input : arr[] = {1, 2, 3, 4, 28}
Output : 84

Input : arr[] = {4, 6, 12, 24, 30}
Output : 120

In this post a different approach is discussed that doesn’t require computation of GCD. Below are steps.

  1. Initialize result = 1
  2. Find a common factors of two or more array elements.
  3. Multiply the result by common factor and divide all the array elements by this common factor.
  4. Repeat steps 2 and 3 while there is a common factor of two or more elements.
  5. Multiply the result by reduced (or divided) array elements.

Illustration :

Let we have to find the LCM of arr[] = {1, 2, 3, 4, 28} We initialize result = 1. 2 is a common factor that appears in two or more elements. We divide all multiples by two and multiply result with 2. arr[] = {1, 1, 3, 2, 14} result = 2 2 is again a common factor that appears in two or more elements. We divide all multiples by two and multiply result with 2. arr[] = {1, 1, 3, 1, 7} result = 4 Now there is no common factor that appears in two or more array elements. We multiply all modified array elements with result, we get. result = 4 * 1 * 1 * 3 * 1 * 7 = 84

Below is the implementation of above algorithm.

// C++ program to find LCM of array without

// using GCD.

#include<bits/stdc++.h>

using namespace std;

// Returns LCM of arr[0..n-1]

unsigned long long int LCM( int arr[], int n)

{

// Find the maximum value in arr[]

int max_num = 0;

for ( int i=0; i<n; i++)

if (max_num < arr[i])

max_num = arr[i];

// Initialize result

unsigned long long int res = 1;

// Find all factors that are present in

// two or more array elements.

int x = 2; // Current factor.

while (x <= max_num)

{

// To store indexes of all array

// elements that are divisible by x.

vector< int > indexes;

for ( int j=0; j<n; j++)

if (arr[j]%x == 0)

indexes.push_back(j);

// If there are 2 or more array elements

// that are divisible by x.

if (indexes.size() >= 2)

{

// Reduce all array elements divisible

// by x.

for ( int j=0; j<indexes.size(); j++)

arr[indexes[j]] = arr[indexes[j]]/x;

res = res * x;

}

else

x++;

}

// Then multiply all reduced array elements

for ( int i=0; i<n; i++)

res = res*arr[i];

return res;

}

// Driver code

int main()

{

int arr[] = {1, 2, 3, 4, 5, 10, 20, 35};

int n = sizeof (arr)/ sizeof (arr[0]);

cout << LCM(arr, n) << "\n" ;

return 0;

}

Output:

420