Holas, te dejo 2 formas de resolver el problema:
* PRIMER METODO:
Existe una propiedad interesante del MCD, el cual sirve para el problema que mencionas:
Sean los enteros positivos: x[1], x[2], x[3], ..., x[n] ; entonces:
MCD( x[1], x[2], x[3], ..., x[n] ) = MCD( MCD( x[1], x[2], ..., x[n-1] ), x[n] )
Esto se puede aplicar recursivamente, hasta llegar a:
MCD( x[1], x[2], x[3], ..., x[n] ) = MCD( MCD( ... MCD( MCD( MCD( x[1], x[2] ), x[3] ), x[4]), ... ), x[n] )
En resumen para hallar el MCD de los N numeros, puedes intentar:
Primero calculas el MCD de x[1] y x[2], luego calculas el MCD del resultado anterior con x[3],
luego calculas el MCD del resultado anterior con x[4], asi sucesivamente hasta el ultimo numero x[n].
En pseudocogido seria asi:
Entero MCD = 1;
// MaximoComunDivisor( a, b ) es el algoritmo de euclides usado para
// hallar el Maximo Comun Divisor de dos enteros positivos.
Para i de 2 hasta n hacer
MCD = MaximoComunDivisor( MCD, x[i] )
Retornar MCD
* SEGUNDO METODO:
Otra propiedad del MCD dice que el máximo común divisor de dos números resulta ser el producto
de sus factores primos comunes elevados al menor exponente.
Es decir sean los numeros: 24, 30, 36
- 24 = ( 2^3 ) * ( 3^1 ) = ( 2^3 ) * ( 3^1 ) * ( 5^0 )
- 30 = ( 2^1 ) * ( 3^1 ) * ( 5^1 ) = ( 2^1 ) * ( 3^1 ) * ( 5^1 )
- 36 = ( 2^2 ) * ( 3^2 ) = ( 2^2 ) * ( 3^2 ) * ( 5^0 )
Por lo tanto el MCD( 24, 30, 36 ) = ( 2^1 ) * ( 3^1 ) * ( 5^0 ) = 6
Esto de puede modelar en un algoritmos, si es que guardamos cada numero en un vector de tamaño N,
y luego ir dividiendo todos los numeros del vector, entre 2, 3, 4, ..., Z, donde z es el menor numero almacenado en el vector:
// Vector donde estan almacenados los numeros de los que se hallara su MCD
Entero[] vector
// Obtenemos el menor elemento del vector, el cual sera el maximo valor por el que dividiremos cada elemento del vector.
Entero menor = MenorElemento( vector )
// Menor de todos los exponentes del factor primo actual
Entero menorExponente = 0
// Valor que almacena el MCD divisor de los numeros
Entero MCD = 1
// Indica si el factor primo actual es un divisor comun de todos los numeros
Booleano esDivisorComun
// "i", indica el factor que verificaremos si es factor comun ( divisor ) a todos los numeros
Para i desde 2 hasta i*i <= menor hacer
esDivisorComun = verdad
j = 1
menorExponente = 0
Mientras( esDivisorComun )
Si( j = n + 1 ) // Si el divisor "i", es comun a todos entonces el menorExponente aumenta 1
menorExponente = menorExponente + 1
j = 1
// Como el i es divisor comun, pasamos a dividir todos los numeros entre i,
// esto tambien afecta a "menor"
Para h de 1 hasta n hacer
vector[ h ] = vector[ h ] / i
FinPara
menor = menor / i
FinSi
Si( vector[ i ] mod i != 0 ) // Si el divisor actual no es comun a todos, pasamos al siguiente divisor
esDivisorComun = falso
Fin_Mientras
// Actualizamos el MCD
MCD = MCD * Potencia( i, menorExponente )
Fin_Para
Si comparamos los 2 algoritmos te puedes dar cuenta de que el primero es mas facil dec codificar ademas
que es de orden O( n log(n) ) , en cambio el segundo es mas "engorroso" para codificar y encima es de orden O( n Raiz( n ) )
( lo cual es mas lento que el primer algoritmo ) .
Donde n es el valor del mayor elemento de los que se desea hallar su MCD.
Espero que te sirvan de algo.
PD: Realmente esos ordenes de los algortimos no son los correctos, ya que estos han sido calculados
en funcion del valor de n y no del tamaño de n.
