Encontrar MCM de más de dos (o arreglos) números sin usar GCD

Dada una array de enteros positivos, encuentre el MCM de los elementos presentes en la array.
Ejemplos: 
 

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

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

Hemos discutido LCM de array usando GCD .
En esta publicación se analiza un enfoque diferente que no requiere el cálculo de GCD. A continuación se muestran los pasos. 
 

1. Inicializar resultado = 1
2. Encuentre un factor común de dos o más elementos de array.
3. Multiplique el resultado por el factor común y divida todos los elementos de la array por este factor común.
4. Repite los pasos 2 y 3 mientras haya un factor común de dos o más elementos.
5. Multiplique el resultado por elementos de array reducidos (o divididos).

Ilustración : 

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

A continuación se muestra la implementación del algoritmo anterior. 
 

// 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;
}

import java.util.Vector;
 
// Java program to find LCM of array without
// using GCD.
class GFG {
 
// Returns LCM of arr[0..n-1]
    static long 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
        long 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<Integer> indexes = new Vector<>();
            for (int j = 0; j < n; j++) {
                if (arr[j] % x == 0) {
                    indexes.add(indexes.size(), 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.get(j)] = arr[indexes.get(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
    public static void main(String[] args) {
        int arr[] = {1, 2, 3, 4, 5, 10, 20, 35};
        int n = arr.length;
        System.out.println(LCM(arr, n));
    }
}

# Python3 program to find LCM of array
# without using GCD.
 
# Returns LCM of arr[0..n-1]
def LCM(arr, n):
     
    # Find the maximum value in arr[]
    max_num = 0;
    for i in range(n):
        if (max_num < arr[i]):
            max_num = arr[i];
 
    # Initialize result
    res = 1;
 
    # Find all factors that are present
    # in two or more array elements.
    x = 2; # Current factor.
    while (x <= max_num):
         
        # To store indexes of all array
        # elements that are divisible by x.
        indexes = [];
        for j in range(n):
            if (arr[j] % x == 0):
                indexes.append(j);
 
        # If there are 2 or more array
        # elements that are divisible by x.
        if (len(indexes) >= 2):
             
            # Reduce all array elements
            # divisible by x.
            for j in range(len(indexes)):
                arr[indexes[j]] = int(arr[indexes[j]] / x);
 
            res = res * x;
        else:
            x += 1;
 
    # Then multiply all reduced
    # array elements
    for i in range(n):
        res = res * arr[i];
 
    return res;
 
# Driver code
arr = [1, 2, 3, 4, 5, 10, 20, 35];
n = len(arr);
print(LCM(arr, n));
 
# This code is contributed by chandan_jnu

// C# program to find LCM of array
// without using GCD.
using System;
using System.Collections;
class GFG
{
 
// Returns LCM of arr[0..n-1]
static long 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
    long 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.
        ArrayList indexes = new ArrayList();
        for (int j = 0; j < n; j++)
        {
            if (arr[j] % x == 0)
            {
                indexes.Add(j);
            }
        }
 
        // If there are 2 or more array elements
        // that are divisible by x.
        if (indexes.Count >= 2)
        {
            // Reduce all array elements divisible
            // by x.
            for (int j = 0; j < indexes.Count; j++)
            {
                arr[(int)indexes[j]] = arr[(int)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
public static void Main()
{
    int []arr = {1, 2, 3, 4, 5, 10, 20, 35};
    int n = arr.Length;
    Console.WriteLine(LCM(arr, n));
}
}
 
// This code is contributed by mits

<?php
// PHP program to find LCM of array
// without using GCD.
 
// Returns LCM of arr[0..n-1]
function LCM($arr, $n)
{
    // Find the maximum value in arr[]
    $max_num = 0;
    for ($i = 0; $i < $n; $i++)
        if ($max_num < $arr[$i])
            $max_num = $arr[$i];
 
    // Initialize result
    $res = 1;
 
    // Find all factors that are present
    // in two or more array elements.
    $x = 2; // Current factor.
    while ($x <= $max_num)
    {
        // To store indexes of all array
        // elements that are divisible by x.
        $indexes = array();
        for ($j = 0; $j < $n; $j++)
            if ($arr[$j] % $x == 0)
                array_push($indexes, $j);
 
        // If there are 2 or more array
        // elements that are divisible by x.
        if (count($indexes) >= 2)
        {
            // Reduce all array elements
            // divisible by x.
            for ($j = 0; $j < count($indexes); $j++)
                $arr[$indexes[$j]] = (int)($arr[$indexes[$j]] / $x);
 
            $res = $res * $x;
        }
        else
            $x++;
    }
 
    // Then multiply all reduced
    // array elements
    for ($i = 0; $i < $n; $i++)
        $res = $res * $arr[$i];
 
    return $res;
}
 
// Driver code
$arr = array(1, 2, 3, 4, 5, 10, 20, 35);
$n = count($arr);
echo LCM($arr, $n) . "\n";
 
// This code is contributed by chandan_jnu
?>

<script>
// Javascript program to find LCM of array without
// using GCD.
 
// Returns LCM of arr[0..n-1]
function LCM(arr, n)
{
    // Find the maximum value in arr[]
    var max_num = 0;
    for (var i = 0; i < n; i++)
        if (max_num < arr[i])
            max_num = arr[i];
 
    // Initialize result
    var res = 1;
 
    // Find all factors that are present in
    // two or more array elements.
    var x = 2;  // Current factor.
    while (x <= max_num)
    {
        // To store indexes of all array
        // elements that are divisible by x.
        var indexes = [];
        for (var j = 0; j < n; j++)
            if (arr[j] % x == 0)
                indexes.push(j);
 
        // If there are 2 or more array elements
        // that are divisible by x.
        if (indexes.length >= 2)
        {
            // Reduce all array elements divisible
            // by x.
            for (var j = 0; j < indexes.length; j++)
                arr[indexes[j]] = arr[indexes[j]]/x;
 
            res = res * x;
        }
        else
            x++;
    }
 
    // Then multiply all reduced array elements
    for (var i = 0; i < n; i++)
        res = res*arr[i];
 
    return res;
}
 
// Driver code
var arr = [1, 2, 3, 4, 5, 10, 20, 35];
var n = arr.length;
document.write( LCM(arr, n) + "<br>");
 
// This code is contributed by rrrtnx.
</script>

Producción: 
 

420

Complejidad de tiempo: O(max * n), donde n representa el tamaño de la array dada y m representa el elemento máximo presente en la array.
Espacio auxiliar: O(n), donde n representa el tamaño de la array dada.

Este artículo es una contribución de Aditya Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.