Algoritmo euclidiano: GCD (mayor divisor común) explicado con ejemplos de C ++ y Java

Para este tema, primero debe conocer el Divisor Común Máximo (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.

Ejemplo-

MCD de 20; 30 = 10   (10 es el número más grande que divide a 20 y 30 con el resto como 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 como 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.

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)

Con los dos conceptos anteriores comprendidos, 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:

Suponiendo que desea calcular el MCD de 1220 y 516, apliquemos el algoritmo euclidiano:

Ejemplo euclidiano

Pseudo código del algoritmo

Paso 1:   Dejado   a, b  ser los dos números

Paso 2:  a mod b = R

Paso 3:   Deja   a = b  y  b = R

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

Paso 5:   MCD = b

Paso 6: Terminar

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; } 

Código JavaScript para realizar GCD mediante recursividad

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

Código C para realizar GCD usando recursividad

int gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a-b, b); return gcd(a, b-a); } 

Código C ++ para realizar GCD-

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

Código Python para realizar GCD mediante recursividad

def gcd(a, b): if b == 0: return a: else: return gcd(b, (a % b)) 

Código Java para realizar GCD mediante recursividad

static int gcd(int a, int b) { if(b == 0) { return a; } 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   n  números de la misma manera.

¿Qué es el algoritmo euclidiano extendido?

Esta es una extensión del algoritmo euclidiano. También calcula los coeficientes x, y tales que

ax + por = mcd (a, b)

xey también se conocen como coeficientes de identidad de Bézout.

código c para el algoritmo euclidiano extendido

struct Triplet{ int gcd; int x; int y; }; Triplet gcdExtendedEuclid(int a,int b){ //Base Case if(b==0){ Triplet myAns; myAns.gcd = a; myAns.x = 1; myAns.y = 0; return myAns; } Triplet smallAns = gcdExtendedEuclid(b,a%b); //Extended euclid says Triplet myAns; myAns.gcd = smallAns.gcd; myAns.x = smallAns.y; myAns.y = (smallAns.x - ((a/b)*(smallAns.y))); return myAns; }