Mínimo común divisor

En algunos problemas se debe encontrar el divisor común mínimo de uno o más números. Sí, el divisor común mínimo, no el máximo. El mímimo común divisor es muy similar al máximo común divisor, en ocasiones es el mismo pero no se deben confundir. El GDC(máximo común divisor) entre 54 y 24 es 6 mientras que el mínimo común divisor es 2.

Para obtener el gcd se puede usar el algoritmo de euclides, el cual en código es:

static int gcd(int a, int b){
if(b==0)return a;
return gcd(b,a%b);
}

Una vez que se tiene el gcd se puede encontrar el divisor común mínimo.

Si r = gcd(a,b) y r = c*d entonces c y d dividen a y b.

De esta forma, lo que debemos hacer es descomponer el gcd en sus factores primos y sacamos el mínimo. De esta forma obtendríamos el mínimo común divisor.

Nota: un problema que se resuelve con esta idea es este.