El Algoritmo de Euclides Sirve Para Obtener El

8/18/2019 El Algoritmo de Euclides Sirve Para Obtener El

1/5

El algoritmo de Euclides sirve para obtener el máximo común

divisor (abreviado normalmente como M.C.D.) de dos números enteros

positivos. El mínimo común múltiplo (M.C.M.), puede obtenerse

también con éste algoritmo, haciendo una sencilla operación con el M.C.D.

obtenido. En este artículo hablamos de cómo programarlo.

uedes encontrar una demostración en línea al !inal de ésta p"gina.

#e llama así por Euclides de $le%andría, un matem"tico griego &ue vivió en

los tiempos del !araón tolomeo ', del &ue nos han &uedado algunos tetos

recopilatorios del saber matem"tico geométrico de su época. *o es &ue

Euclides escribiera tal cual éste algoritmo, sino &ue, aparentemente, de%ó

escritas algunas relaciones entre números &ue son la base de lo &ue ho

llamamos MCD.

Es uno de los algoritmos típicos &ue los pro!esores de programación ponen a

sus alumnos para practicar el bucle repetir+mientras o hacer+hasta (repeat+

until o do+hile) pasando valores de una iteración a otra del bucle.

Máximo Común Divisor (MCD)

El m"imo común divisor de dos números enteros positivos a b es otro

número entero positivo c tal &ue si dividimos a/c b/c, los restos de las

divisiones son -, adem"s no eiste otro número maor &ue c &ue tenga esta

caracterísitica. Como nos decían en el cole, el máximo común dívisor

(mcd) de dos enteros a y b es el mayor entero c que divide exactamente

a a y b .

$un&ue en el colegio nos ense/an a encontrar el mcd a partir de lade a b,

esa no es una buena !orma de obtener el mcd computacionalmente, a &ue el

algoritmo para descomponer en !actores primos es mu costoso, en términosde computación. El algoritmo de Euclides es bastante m"s e!iciente para

obtener el mcd, aun&ue normalmente sorprende un poco cuando tenemos

contacto con él por primera ve0.

El algoritmo de Euclides es el siguiente:

http://latecladeescape.com/h/2015/09/algoritmo-de-euclides#demohttp://latecladeescape.com/h/2015/09/algoritmo-de-euclides#demohttp://es.wikipedia.org/wiki/Euclideshttp://es.wikipedia.org/wiki/Euclideshttp://latecladeescape.com/h/2015/09/algoritmo-de-euclides#demo


2/5

#iendo a b dos enteros positivos tales &ue a>b, comen0amos

dividiendo a/b, con lo &ue obtendremos un resto r1 un cociente q 1.

1acemos la operación q 1=a/b, utili0ando la división entera, sin decimales....

pero realmente no sólo nos interesa el resultado o cociente de la división,

sino &ue nos interesa también el resto, así &ue la operación la vamos a

reescribir de otra !orma.

Es importante &ue llamemos a al maor de los dos números (siempre el

maor va a ser a). Debemos dividir a entre b obtener un cociente (al &ue

llamaremos q 1) un resto (al &ue llamaremos r1).

2btenidos ese cociente ese resto, se cumple &ue3

a=q 1·b+r1

4os lengua%es de programación suelen tener un operador para e!ectuar la

división entera (con lo &ue obtendremos &5. or e%emplo, en C63 q1=a/b;),

otro para obtener el resto o módulo de la división (con lo &ue obtendremos

r5. or e%emplo, en C63 r1=a%b;5).

$ partir de esa primera división, es necesario repetir un proceso3

• dividir el numero &ue !ue divisor en el paso anterior entre el restoobtenido en el paso anterior

• despreciar el cociente

• si el resto obtenido esta ve0 es -, el mcd es el divisor de esta operacion,

es decir, el último resto no nulo (recordemos &ue el divisor de esta operación

!ué el resto en la anterior.

• #i el resto no es -, ir al primer paso

Es un poco engorroso la primera ve0, pero realmente es un algoritmo mu

sencillo.

#iguiendo con el e%emplo, en la segunda iteración, dividiríamos

b7r5 obteniendo un resto r8(hacemos la operación de división para obtener el

http://latecladeescape.com/h/2015/09/algoritmo-de-euclides#fn:1http://latecladeescape.com/h/2015/09/algoritmo-de-euclides#fn:1


3/5

cociente, al &ue llamamos &8 la de obtener el resto, al &ue llamamos r8), de

tal manera &ue se cumpliría lo siguiente3

b=q 2·r1+r2

En la tercera iteración, dividimos r57r8 obteniendo un resto r9

r1=q 3·r2+r3

: se continúa así hasta obtener un resto -. El último resto (llamémosle r; )

distinto de cero es el mcd.

rk2=q k ·rk1+rk rk1=q k+1·rk +!

rk es el mcd(a,b)

Es decir, empe0amos dividiendo un número entre otro (obteniendo el resto

también, no sólo el cociente), a partir de ahí, seguimos dividiendo elnúmero m"s pe&ue/o entre el resto &ue nos ha salido... continuamos

dividiendo por el resto anterior una ve0 otra hasta &ue en ese proceso

repetitivo obtengamos un resto &ue sea -.


4/5

int iaux; //auxiliar a = Math.Abs(a); //tomamos alor absoluto b = Math.Abs(b); int i!=Math.Max(a,b); //i! = el m"s rande int i$=Math.Min(a,b); //i$ = el m"s %e&ue'o do

{ iaux = i$; //uardar diisor i$ = i! i$; //resto %asa a diisor i! = iaux; //diisor %asa a diidendo *hile (i$ += ); return i!; //ultimo resto no nulo

$l principio cuesta un poco de coger... te recomiendo hacer una tra0a

mentalmente (o me%or, aud"ndote de papel).

?e dar"s cuenta de cómo se van despla0ando los valores a medida &ue

vamos dividiendo hasta obtener el resto -... aun&ue, realmente... no estamos

utili0ando los cocientes, sino sólo los restos @+)

$un&ue en la introducción hemos mencionado la división (7), realmente no

es del todo cierto... sólo &ueremos los restos, no el cociente...(operador

módulo o resto3 A en C6). 1emos introducido esta pe&ue/a trampa en la

eplicación (pero no en el código) por&ue cuando dividimos a mano,

realmente en la misma operación de división obtenemos dos resultados a la

ve03 por un lado el cociente por otro, el resto. #in embargo, los lengua%es de

programación hacen cada una de esas cosas por separado3 pueden obtener

un cociente sin necesidad de obtener un resto al revés, obtener un resto sin

necesidad de dividir... así &ue en nuestro algoritmo no dividimos realmente3

sólo obtenemos el resto. #i lo hiciéramos a mano, tendríamos &ue dividir,

con lo &ue obtendríamos el cociente el resto simult"neamente, pero

despreciaríamos el cociente nos &uedaríamos sólo con el resto.M"nimo Común Múlti#lo! (MCM)

Mu relacionado con el m"imo común divisor est" el mínimo común

múltiplo (mcm).


5/5

El mcm de dos enteros positivos a b es un valor c entero positivo tal &ue

al dividir c7a c7b el resto es -, adem"s no eiste otro número menor &ue c

&ue cumpla esta condición.

1a una relación mu sencilla entre mcm mcd. Es ésta3

mcm"a#b$="a·b$/mcd"a#b$

$sí pues, también podemos obtener el mcm mediante el algoritmo de

Euclides.

static int EuclidesMCM(int a, int b){ return (a / EuclidesMCD(a, b)) - b;

2bserva &ue primero se divide a entre el mcd, en lugar de multiplicar ab.

Esto se hace para evitar un posible desbordamiento al multiplicar a b.

Demo

Documents

El Algoritmo de Euclides Sirve Para Obtener El