GCD de más de dos (o array) números

Dada una array de números, encuentre el MCD de los elementos de la array. En una publicación anterior encontramos GCD de dos números .

Ejemplos:

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

Input  : arr[] = {2, 4, 6, 8}
Output : 2

El MCD de tres o más números es igual al producto de los factores primos comunes a todos los números, pero también se puede calcular tomando repetidamente los MCD de pares de números. 

gcd(a, b, c) = gcd(a, gcd(b, c)) 
             = gcd(gcd(a, b), c) 
             = gcd(gcd(a, c), b)

Para una array de elementos, hacemos lo siguiente. También verificaremos el resultado si el resultado en cualquier paso se convierte en 1, solo devolveremos el 1 como mcd (1, x) = 1. 

result = arr[0]
For i = 1 to n-1
   result = GCD(result, arr[i])

A continuación se muestra la implementación de la idea anterior.

// C++ program to find GCD of two or
// more numbers
#include <bits/stdc++.h>
using namespace std;
 
// Function to return gcd of a and b
int gcd(int a, int b)
{
  if (a == 0)
    return b;
  return gcd(b % a, a);
}
 
// Function to find gcd of array of
// numbers
int findGCD(int arr[], int n)
{
  int result = arr[0];
  for (int i = 1; i < n; i++)
  {
    result = gcd(arr[i], result);
 
    if(result == 1)
    {
    return 1;
    }
  }
  return result;
}
 
// Driver code
int main()
{
  int arr[] = { 2, 4, 6, 8, 16 };
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << findGCD(arr, n) << endl;
  return 0;
}

// Java program to find GCD of two or
// more numbers
 
public class GCD {
    // Function to return gcd of a and b
    static int gcd(int a, int b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }
 
    // Function to find gcd of array of
    // numbers
    static int findGCD(int arr[], int n)
    {
        int result = arr[0];
        for (int element: arr){
            result = gcd(result, element);
 
            if(result == 1)
            {
               return 1;
            }
        }
 
        return result;
    }
 
    public static void main(String[] args)
    {
        int arr[] = { 2, 4, 6, 8, 16 };
        int n = arr.length;
        System.out.println(findGCD(arr, n));
    }
}
 
// This code is contributed by Saket Kumar

# GCD of more than two (or array) numbers
 
# Function implements the Euclidean
# algorithm to find H.C.F. of two number
def find_gcd(x, y):
     
    while(y):
        x, y = y, x % y
     
    return x
         
# Driver Code       
l = [2, 4, 6, 8, 16]
 
num1 = l[0]
num2 = l[1]
gcd = find_gcd(num1, num2)
 
for i in range(2, len(l)):
    gcd = find_gcd(gcd, l[i])
     
print(gcd)
 
# Code contributed by Mohit Gupta_OMG

// C# program to find GCD of
// two or more numbers
using System;
 
public class GCD {
     
    // Function to return gcd of a and b
    static int gcd(int a, int b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }
 
    // Function to find gcd of
    // array of numbers
    static int findGCD(int[] arr, int n)
    {
        int result = arr[0];
        for (int i = 1; i < n; i++){
            result = gcd(arr[i], result);
 
            if(result == 1)
            {
               return 1;
            }
        }
 
        return result;
    }
     
    // Driver Code
    public static void Main()
    {
        int[] arr = { 2, 4, 6, 8, 16 };
        int n = arr.Length;
        Console.Write(findGCD(arr, n));
    }
}
 
// This code is contributed by nitin mittal

<?php
// PHP program to find GCD of two or
// more numbers
 
// Function to return gcd of a and b
function gcd( $a, $b)
{
    if ($a == 0)
        return $b;
    return gcd($b % $a, $a);
}
 
// Function to find gcd of array of
// numbers
function findGCD($arr, $n)
{
    $result = $arr[0];
 
    for ($i = 1; $i < $n; $i++){
        $result = gcd($arr[$i], $result);
 
        if($result == 1)
        {
           return 1;
        }
    }
    return $result;
}
 
// Driver code
$arr = array( 2, 4, 6, 8, 16 );
$n = sizeof($arr);
echo (findGCD($arr, $n));
 
// This code is contributed by
// Prasad Kshirsagar.
?>

<script>
 
// Javascript program to find GCD of two or
// more numbers
 
// Function to return gcd of a and b
function gcd(a, b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
 
// Function to find gcd of array of
// numbers
function findGCD(arr, n)
{
    let result = arr[0];
    for (let i = 1; i < n; i++)
    {
        result = gcd(arr[i], result);
 
        if(result == 1)
        {
        return 1;
        }
    }
    return result;
}
 
// Driver code
 
    let arr = [ 2, 4, 6, 8, 16 ];
    let n = arr.length;
    document.write(findGCD(arr, n) + "<br>");
 
// This is code is contributed by Mayank Tyagi
 
</script>

2

Complejidad de tiempo: O(N * log(N)) , donde N es el elemento más grande de la array
Espacio auxiliar: O(1)

Método recursivo: Implementación del algoritmo recursivamente:

#include <bits/stdc++.h>
using namespace std;
 
// recursive implementation
int GcdOfArray(vector<int>& arr, int idx)
{
    if (idx == arr.size() - 1) {
        return arr[idx];
    }
    int a = arr[idx];
    int b = GcdOfArray(arr, idx + 1);
    return __gcd(
        a, b); // __gcd(a,b) is inbuilt library function
}
 
int main()
{
    vector<int> arr = { 1, 2, 3 };
    cout << GcdOfArray(arr, 0) << "\n";
 
    arr = { 2, 4, 6, 8 };
    cout << GcdOfArray(arr, 0) << "\n";
    return 0;
}

import java.util.*;
class GFG
{
   
    // Recursive function to return gcd of a and b 
    static int __gcd(int a, int b) 
    { 
        return b == 0? a:__gcd(b, a % b);    
    }
   
// recursive implementation
static int GcdOfArray(int[] arr, int idx)
{
    if (idx == arr.length - 1) {
        return arr[idx];
    }
    int a = arr[idx];
    int b = GcdOfArray(arr, idx + 1);
    return __gcd(
        a, b); // __gcd(a,b) is inbuilt library function
}
 
public static void main(String[] args)
{
   int[] arr = { 1, 2, 3 };
    System.out.print(GcdOfArray(arr, 0)+ "\n");
 
    int[] arr1 = { 2, 4, 6, 8 };
    System.out.print(GcdOfArray(arr1, 0)+ "\n");
}
}
 
// This code is contributed by gauravrajput1

# To find GCD of an array by recursive approach      
import math
 
# Recursive Implementation
def GcdOfArray(arr, idx):
    if idx == len(arr)-1:
        return arr[idx]
       
    a = arr[idx]
    b = GcdOfArray(arr,idx+1)
     
    return math.gcd(a, b)
 
# Driver Code
arr = [1, 2, 3]
print(GcdOfArray(arr,0))
 
arr = [2, 4, 6, 8]
print(GcdOfArray(arr,0))
 
# Code contributed by Gautam goel (gautamgoel962)

// To find GCD of an array by recursive approach
using System;
  
public class GCD {
      
    // Function to return gcd of a and b
    static int gcd(int a, int b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }
  
    // Recursive Implementation
    static int GcdOfArray(int[] arr, int idx)
    {
        if(idx==arr.Length-1)
        {
            return arr[idx];
        }
        int a = arr[idx];
        int b = GcdOfArray(arr, idx + 1);
        return gcd(a,b);
         
    }
      
    // Driver Code
    public static void Main()
    {
        int[] arr = { 1,2,3 };
        Console.Write(GcdOfArray(arr, 0)+"\n");
         
        int[] arr1 = { 2,4,6,8 };
        Console.Write(GcdOfArray(arr1, 0));
    }
}
  
// This code is contributed by adityapatil12

// JavaScript code to implement this approach
 
// function to calculate gcd
function gcd(a, b)
{
    if (!b)
       return a;
    return gcd(b, a % b);
}
 
// recursive implementation
function GcdOfArray(arr, idx)
{
    if (idx == arr.length - 1) {
        return arr[idx];
    }
    var a = arr[idx];
    var b = GcdOfArray(arr, idx + 1);
    return gcd(a, b);
}
 
// Driver Code
var arr = [ 1, 2, 3 ];
console.log(GcdOfArray(arr, 0));
 
arr = [ 2, 4, 6, 8 ];
console.log(GcdOfArray(arr, 0));
 
// This code is contributed by phasing17

1
2

Complejidad de tiempo: O(N * log(N)), donde N es el elemento más grande de la array
Espacio auxiliar : O(N)

Este artículo es una contribución de DANISH_RAZA . 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.