Implementación de algoritmos de teoría de números/Algoritmo de Euclides

El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (mcd) entre dos números enteros. Fue originalmente descrito por Euclides en la proposición 2 del libro VII de Elementos de Euclides.

Descripción formal editar

Versión recursiva editar

Utilizando recursión, se puede expresar el algoritmo de manera natural:

 función  
   si   
     devolver  
   si no
     devolver  

Versión iterativa editar

La versión iterativa es más eficiente para la implementación en una computadora:

función  
  mientras   hacer
     
     
     
  devolver  

Versión original editar

El algoritmo original descrito por Euclides trataba el problema de manera geométrica; usaba la substracción repetida en lugar del residuo de la división. Esta versión es significativamente menos eficiente:

 función  
   mientras   hacer
     si  
        
     si no
        
   devolver  

Implementación en distintos lenguajes de programación editar

En lenguaje C editar

(versión recursiva)

 unsigned int mcd(unsigned int a, unsigned int b){
     return (b == 0)? a : mcd(b, a % b);
 }

(versión iterativa)

 unsigned int mcd(unsigned int a, unsigned int b){
     unsigned int t;
     while (a > 0){
         t = a;
         a = b % a;
         b = t;
     }
     return b;
 }

editar

(versión recursiva)

para mcd :a :b
 si :b = 0 [
  devuelve :a
 ] sino [
  devuelve mcd :b resto :a :b
 ]
fin

(versión iterativa)

para mcd :a :b
 mientras [:a > 0] [
  haz "t :a
  haz "a resto :b :a
  haz "b :t
 ]
 devuelve :b
fin

En lenguaje Visual Basic 8 editar

(versión iterativa)

 Public Function mcd(a As UInteger, b As UInteger) As UInteger
     Dim t As UInteger
     While a > 0
         t = a
         a = b Mod a
         b = t
     End While
     Return b
 End Function

En lenguaje Haskell editar

(versión recursiva)

mcd::Int->Int->Int
mcd a 0 = a
mcd a b = mcd b (mod a b)

En lenguaje Pascal editar

(versión iterativa)

 function MCD(a , b : integer): integer;
 var
   t:integer;
 begin
     while a > 0 do
     begin
       t := a;
       a := b mod a;
       b := t;
     end;
   result:=b;
 end;

En lenguaje Java editar

(versión iterativa)

	public MCD(int a, b,  t) {
	  while(a>0){
	   t=a;
	   a=b%a;
	   b=t;
	  }
	  System.out.println("El maximo comun divisor es: "+b);
 	 }

En lenguaje Python editar

(versión recursiva)

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