# 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);`

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

` ` `return` `0;`

`}`

Output:

420