CodeUtility
Haz que programar sea más fácil.
Algoritmos en Python

Euclidean GCD Algorithm in Python

Find the greatest common divisor in a few steps with Euclid's remainder trick, then compare with math.gcd.

  • Intermedio
  • 2 min de lectura
  • 1 ejemplo ejecutable
Lo que aprenderás
  • What the GCD is
  • Euclid's algorithm
  • math.gcd in the standard library
Ejecutar en el compilador de Python →
gcd(48, 18)
  1. 48 % 18 = 12→ (18, 12)
  2. 18 % 12 = 6→ (12, 6)
  3. 12 % 6 = 0→ gcd = 6

Replace the pair with (b, a % b)

El máximo común divisor (MCD) de dos enteros es el mayor entero positivo que divide a ambos. El algoritmo de Euclides encuentra el MCD muy rápido gracias a una propiedad sencilla: el MCD de a y b es igual al MCD de b y el resto de dividir a entre b.

Puntos clave

  1. gcd(a, b) equals gcd(b, a % b).
  2. Repeat until the remainder is 0; the other number is the answer.
  3. math.gcd(48, 18) gives the same result.

¿Cuándo se usa?

  • Desarrollar tu forma de pensar y entender paso a paso cómo funciona un algoritmo.
  • Elegir el enfoque adecuado cuando hay que procesar muchos datos o acelerar un programa.
  • Prepararte para exámenes, ejercicios y entrevistas de programación.

Código de ejemplo

Ejecutar código →
main.py
def gcd(first, second):
    while second:
        first, second = second, first % second
    return abs(first)

print(gcd(48, 18))
Obtén un botón Run para este ejemplo

Resultado de la ejecución

6

Explicación del código

En cada paso, la pareja (first, second) se sustituye por (second, first % second). Cuando el resto vale 0, el valor que queda en first es el MCD, así que el de 48 y 18 es 6. La función abs() garantiza que el resultado sea siempre positivo. El número de pasos crece muy despacio con el tamaño de los números, aproximadamente O(log n).

Cambia los valores y ejecuta el programa en el compilador Python online de CodeUtility sin instalar Python.

Ejercicios de práctica

Prueba a modificar el código siguiendo las ideas de abajo. Cambiar el código y ver el resultado te ayudará a entender la lección mucho mejor que solo leerla.

  1. Prueba con una lista vacía, una lista de un solo elemento y una lista con repetidos.
  2. Muestra el estado después de cada paso para ver el algoritmo en acción.
  3. Mide el tiempo de ejecución con 100, 1.000 y 10.000 elementos y compáralo con otra solución.
Ejecutar en el compilador de Python →

Practica con un reto

Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.

Todos los retos