Una implementación sencilla del algoritmo de Euclides para hallar el máximo común divisor entre dos números.

Recordemos que la operación mod (o “módulo”) retorna el resto de la división. Por ejemplo: 5 mod 2 retornará 1, ya que es el resto de dividir 5 / 2.

Algoritmo de euclides

Click aquí para una versión accesible de la infografía (apta para lectores electrónicos)

Algoritmo de Euclides: máximo común divisor.

Pseudocódigo:

while n ≠ 0:
  r ← m mod n
  m ← n
  n ← r
return m

Entrada: dos números enteros positivos donde ninguno es cero: m y n.

Salida: mayor divisor común de m y n.




💻 Implementación en Python