GCD, LCM y el algoritmo de Euclides
Calcule divisores de forma rápida y correcta
GCD, LCM y el algoritmo de Euclides es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
Por qué importan los divisores
Muchos problemas de concursos dependen de los factores compartidos por dos números. La herramienta más útil en este caso es el MCD, el máximo común divisor. 🔢
Qué significa MCD
El MCD de dos enteros es el número más grande que divide a ambos sin dejar resto. Para 12 y 18 es 6, porque 6 divide exactamente a los dos.
La forma lenta
Podría probar todos los números, empezando por el menor valor y descendiendo, hasta encontrar uno que divida a ambos. Funciona, pero es demasiado lento para entradas grandes.
La idea euclídea
El algoritmo de Euclides es la forma rápida. Su idea clave es que el MCD de a y b es igual al MCD de b y el resto de dividir a entre b.
La recurrencia
Repita el paso de intercambio y módulo hasta que el resto sea cero. El último valor distinto de cero es su respuesta: el MCD.
gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = aEscriba el código usted mismo
Un bucle corto sustituye el par repetidamente hasta que b llega a cero. Se ejecuta en aproximadamente log pasos, con una rapidez enorme incluso para números muy grandes.
def gcd(a, b):
while b:
a, b = b, a % b
return aUse la biblioteca estándar
Rara vez tendrá que implementarlo desde cero. Python incluye math.gcd, que es correcto, rápido y gestiona por usted los argumentos cero.
from math import gcd
print(gcd(12, 18))Del MCD al MCM
El MCM, mínimo común múltiplo, es el número más pequeño divisible por ambos valores. Está directamente relacionado con el MCD que acaba de calcular.
La fórmula del MCM
Multiplique los dos números y divida el resultado entre su MCD. Divida siempre primero para evitar desbordamientos en productos muy grandes.
def lcm(a, b):
return a // gcd(a, b) * bMCD de una lista completa
Para calcular el MCD acumulado de muchos números, encadene las operaciones por pares. reduce de Python aplica math.gcd de izquierda a derecha sobre la lista.
from functools import reduce
from math import gcd
g = reduce(gcd, nums)Gestione el caso cero
Por definición, gcd(a, 0) es igual a a, y gcd(0, 0) es 0. Conocer este caso límite evita que los bucles se comporten mal con una entrada vacía.
Comprobación rápida
Es el momento de confirmar el paso euclídeo fundamental.
Repaso
Ahora puede calcular el MCD con el algoritmo de Euclides en pasos logarítmicos, obtener el MCM a partir de él y calcular ambos de forma acumulada en una lista. ✅
Preguntas frecuentes
¿La lección «GCD, LCM y el algoritmo de Euclides» es gratis?
Sí — el texto completo de «GCD, LCM y el algoritmo de Euclides» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «GCD, LCM y el algoritmo de Euclides»?
Calcule divisores de forma rápida y correcta Practicas Competitive Programming Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «GCD, LCM y el algoritmo de Euclides»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- GCD, LCM y el algoritmo de Euclides
- Prueba de primalidad hasta sqrt(n)
- Criba de Eratóstenes
- Factorización prima y divisores