Algoritmo De Euclides

algoritmo de Euclides

Algoritmo de Euclides
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.
Se llama asípor Euclides de Alejandría , un matemático griego que vivió en los tiempos del faraón Ptolomeo I, del que nos han quedado algunos textos recopilatorios del saber matemático y geométrico de su época.No es que Euclides escribiera tal cual éste algoritmo, sino que, aparentemente, dejó escritas algunas relaciones entre números que son la base de lo que hoy llamamos MCD.
Es uno de los algoritmostípicos que los profesores de programación ponen a sus alumnos para practicar el bucle repetir-mientras o hacer-hasta (repeat-until o do-while) pasando valores de una iteración a otra del bucle.El mínimo común múltiplo (M.C.M.), puede obtenerse también con éste algoritmo, haciendo una sencilla operación con el resultado.

Máximo Común Divisor
El máximo común divisor de dos números enterospositivos a y b es otro número entero positivo c tal que si dividimos a/c y b/c, los restos de las divisiones son 0, y además no existe otro número mayor que c que tenga esta caracterísitica. Como nos decían enel "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.
Aunque en el colegio nos enseñan a encontrar el mcd a partir de la descomposiciónen factores primos de a y b, esa no es una buena forma de obtener el mcd computacionalmente, ya que el algoritmo para descomponer en factores primos es muy costoso, en términos de computación. Elalgoritmo de Euclides es bastante más eficiente para obtener el mcd, aunque normalmente sorprende un poco cuando tenemos contacto con él por primera vez.
El algoritmo de Euclides es el siguiente.Algoritmo de Euclides
Siendo a y b dos enteros positivos tales que a>b, comenzamos dividiendo a/b, con lo que obtendremos un resto r1 y un cociente q1. Hacemos la operación q1=a/b, utilizando la...