Algoritmo Euclideano
El algoritmo euclidiano es una forma especial de encontrar el máximo factor común de dos enteros.
División con residuos
Esto utiliza el método de división con residuos (no se necesitan decimales ni fracciones).
Ejemplo: 7 dividido entre 2
7 ÷ 2 = 3 R 1
7 se puede dividir en 2 partes iguales de 3 cada una y sobra 1.
Así que estamos hallando cuántas veces un número cabe exactamente en el otro y cuánto sobra.
Ejemplo: 35 dividido entre 10
35 ÷ 10 = 3 R 5
El algoritmo euclidiano
El algoritmo funciona continuando haciendo este tipo de división hasta que obtengamos un resto de cero. Y cada vez reducimos el tamaño de los números.
Para encontrar el máximo común divisor de a y b, mfc(a,b), asegúrate de que a > b y luego:
Calcula a/b = n R r-
En otras palabras, divide a por b y encuentra n (el número entero de veces que b cabe en a) y el resto r.
- Sea a=b y b=r
- Repite hasta que r=0
El último valor de b es el mfc de los dos enteros originales.
Ejemplo: encontrar mfc(35,10), el máximo factor común de 35 y 10
El residuo es 0, por lo que el mfc de 35 y 10 es 5.
Así que seguimos intentando dividir hasta que obtengamos un residuo de cero que nos diga "¡oye, ese último valor b divide perfectamente!" y en ese momento hemos terminado.
Otro ejemplo:
Ejemplo: encontrar el máximo factor común de 42 y 112
Intercambia a y b de modo que a > b: a=112, b=42:
El residuo es 0, por lo que el mfc de 42 y 112 es 14.
Un ejemplo más:
Ejemplo: encontrar el máximo factor común de 1512 y 444
Intercambia a y b de modo que a > b: a=112, b=42:
El residuo es 0, por lo que el mfc de 1512 y 444 es 12.
El algoritmo en JavaScript:
function gcf(a, b) {
while (b != 0) {
t = b;
b = a % b;
a = t;
}
return a;
}
¡Refuerza tu aprendizaje resolviendo los siguientes retos sobre este tema! (Nota: están en inglés).
