Cómo usar el algoritmo euclidiano para encontrar el máximo divisor común (MCD)

Para este tema, primero debe conocer el máximo divisor común (GCD) y la operación MOD.

Máximo divisor común (GCD)

El MCD de dos o más enteros es el entero más grande que divide cada uno de los enteros de manera que su resto sea cero.

He aquí un ejemplo:

MCD de 20; 30 = 10 (10 es el número más grande que divide a 20 y 30 con el resto de 0)

MCD de 42, 120, 285 = 3 (3 es el número más grande que divide a 42, 120 y 285 con el resto de 0)

Operación "mod"

La operación mod le da el resto cuando se dividen dos enteros positivos. Lo escribimos de la siguiente manera:

A mod B = R

Esto significa que dividir A por B te da el resto R. Esto es diferente a tu operación de división que te da el cociente.

He aquí un ejemplo:

7 mod 2 = 1 (Dividir 7 entre 2 da el resto 1)

42 mod 7 = 0 (Dividiendo 42 entre 7 da el resto 0)

Si comprende los dos conceptos anteriores, comprenderá fácilmente el algoritmo euclidiano.

Algoritmo euclidiano para el máximo divisor común (GCD)

El algoritmo euclidiano encuentra el MCD de 2 números.

Comprenderá mejor este algoritmo viéndolo en acción. Suponiendo que desea calcular el MCD de 1220 y 516, apliquemos el algoritmo euclidiano.

Pseudo código del algoritmo:

Paso 1: Dejado a, bser los dos números

Paso 2: a mod b = R

Paso 3: Deja a = byb = R

Paso 4: repita los pasos 2 y 3 hasta que a mod bsea ​​mayor que 0

Paso 5: MCD = b

Paso 6: Terminar

Aquí está el código Javascript para realizar GCD:

function gcd(a, b) { var R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; }

Aquí está el código Javascript para realizar GCD usando recursividad:

function gcd(a, b) { if (b == 0) return a; else return gcd(b, (a % b)); }

También puede usar el algoritmo euclidiano para encontrar MCD de más de dos números. Dado que GCD es asociativo, la siguiente operación es válida:  GCD(a,b,c) == GCD(GCD(a,b), c)

Calcula el MCD de los dos primeros números, luego encuentra el MCD del resultado y el siguiente número. Ejemplo:GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

Puede encontrar GCD de nnúmeros de la misma manera.