#005 Mínimo común múltiplo

MCM: Mínimo Común Múltiplo

El MCM de varios números es el menor número que es múltiplo de todos ellos. Es decir, el menor número divisible por todos.

Verificando el ejemplo: MCM(1-10) = 2520

1

2520 ÷ 1 = 2520 ✓

Todo número es divisible por 1

2

2520 ÷ 2 = 1260 ✓

2520 es par

3

2520 ÷ 7 = 360 ✓

El caso menos obvio: 7 × 360 = 2520

4

2520 ÷ 10 = 252 ✓

Todos del 1 al 10 dividen exactamente

Los números del 1 al 20

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Primos en morado: 2, 3, 5, 7, 11, 13, 17, 19

MCM(a, b) = (a \times b) / MCD(a, b) MCD = Máximo Común Divisor

Conceptos clave

🔢 MCM 🔗 MCD 💜 Primos ➗ Divisibilidad

La estrategia

Podemos probar números hasta encontrar uno divisible por todos, o calcular el MCM acumulando de dos en dos.

Relación clave: MCM(a, b) = a × b ÷ MCD(a, b). El MCD se calcula con el algoritmo de Euclides.

Variante A: probar múltiplos de 20

El resultado debe ser múltiplo de 20. Probamos 20, 40, 60... hasta encontrar uno divisible por todos.

Python

def divisible_por_todos(n, hasta):
    """Comprueba si n es divisible por todos los números del 1 al hasta"""
    for i in range(1, hasta + 1):
        if n % i != 0:
            return False
    return True

# Buscar el menor múltiplo de 20 divisible por todos
n = 20
while True:
    if divisible_por_todos(n, 20):
        break
    n = n + 20          # Siguiente múltiplo de 20

print(n)

Pulsa "Ejecutar" para ver el resultado

Variante B: MCD con Euclides

Implementamos MCD manualmente y calculamos MCM acumulando.

Python

def mcd(a, b):
    """Máximo Común Divisor usando algoritmo de Euclides"""
    while b != 0:
        a, b = b, a % b
    return a

def mcm(a, b):
    """Mínimo Común Múltiplo"""
    return a * b // mcd(a, b)

# Calcular MCM acumulado del 1 al 20
resultado = 1
for i in range(1, 21):
    resultado = mcm(resultado, i)
    print(f"MCM(1..{i}) = {resultado}")

print(f"\nResultado: {resultado}")

Pulsa "Ejecutar" para ver el resultado

Variante C: usando math.gcd

Python tiene math.gcd incorporado. Lo usamos directamente.

Python

from math import gcd

def mcm(a, b):
    return a * b // gcd(a, b)

resultado = 1
for i in range(1, 21):
    resultado = mcm(resultado, i)

print(resultado)

Pulsa "Ejecutar" para ver el resultado

¿Cuál elegir?

Variante	Iteraciones	Ventaja
A: probar múltiplos	~11.6 millones	Intuitiva
B: MCD manual	~60	Enseña Euclides
C: math.gcd	~60	Más corta

Resultado (las tres variantes) 232792560

Conceptos clave

1

`a, b = b, a % b`

Algoritmo de Euclides. Reemplaza a por b, y b por el resto. Cuando b es 0, a es el MCD.

2

`a * b // mcd(a, b)`

Fórmula del MCM. El producto dividido por el MCD da el MCM.

3

`from math import gcd`

Importar función. Traemos gcd del módulo math de Python.

4

MCM acumulado

MCM(1,2,3) = MCM(MCM(1,2), 3). Podemos ir acumulando de dos en dos.

Conceptos de Python aprendidos

📦 import 🔧 math.gcd 🔄 Algoritmo Euclides 🎯 Funciones

reduce: acumular con función

reduce(f, [a,b,c,d]) calcula f(f(f(a,b),c),d). Perfecto para acumular MCM.

Python

from math import gcd
from functools import reduce

mcm = lambda a, b: a * b // gcd(a, b)

resultado = reduce(mcm, range(1, 21))

print(resultado)

Pulsa "Ejecutar" para ver el resultado

Desglose

1

`from functools import reduce`

reduce aplica una función acumulativamente a una secuencia.

2

`reduce(mcm, range(1, 21))`

Equivale a: mcm(mcm(mcm(1,2),3),4)...20)

Aspecto	for loop	reduce
Líneas	4	1
Estilo	Imperativo	Funcional
Legibilidad	Más clara	Más compacta

Resultado 232792560

Conceptos aprendidos

🔄 reduce λ lambda 📦 functools 🎭 Programación funcional

MCM como producto de potencias de primos

El MCM de 1 a n es el producto de la mayor potencia de cada primo que no exceda n.

Primos ≤ 20 y sus mayores potencias

2 4 = 16

3 2 = 9

5 1 = 5

7 1 = 7

11 1

13 1

17 1

19 1

?

¿Por qué 2⁴ = 16?

Porque 16 ≤ 20 pero 32 > 20. Necesitamos 16 para que 16 divida al MCM.

MCM = 2⁴ \times 3² \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 = 16 \times 9 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 = 232792560

Python

def es_primo(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def mcm_hasta(n):
    """MCM de 1 a n usando potencias de primos"""
    resultado = 1

    for p in range(2, n + 1):
        if es_primo(p):
            # Encontrar la mayor potencia de p que no exceda n
            potencia = p
            while potencia * p <= n:
                potencia *= p
            resultado *= potencia
            print(f"Primo {p}: mayor potencia ≤ {n} es {potencia}")

    return resultado

print(f"\nMCM(1..20) = {mcm_hasta(20)}")

Pulsa "Ejecutar" para ver el resultado

Comparativa de rendimiento

Método	Operaciones	Complejidad
Probar múltiplos	~232 millones	O(MCM × n)
MCM iterativo	~60	O(n log n)
Potencias de primos	~30	O(n)

Probar múltiplos ~232M operaciones

Potencias de primos ~30 operaciones

Resultado 232792560

Conceptos aprendidos

💜 Factorización prima 📐 Potencias 🧮 Teoría de números ⚡ O(n)

MCM: Mínimo Común Múltiplo

Verificando el ejemplo: MCM(1-10) = 2520

2520 ÷ 1 = 2520 ✓

2520 ÷ 2 = 1260 ✓

2520 ÷ 7 = 360 ✓

2520 ÷ 10 = 252 ✓

Los números del 1 al 20

Conceptos clave

La estrategia

Variante A: probar múltiplos de 20

Variante B: MCD con Euclides

Variante C: usando math.gcd

¿Cuál elegir?

Conceptos clave

a, b = b, a % b

a * b // mcd(a, b)

from math import gcd

MCM acumulado

Conceptos de Python aprendidos

reduce: acumular con función

Desglose

from functools import reduce

reduce(mcm, range(1, 21))

Conceptos aprendidos

MCM como producto de potencias de primos

Primos ≤ 20 y sus mayores potencias

¿Por qué 2⁴ = 16?

Comparativa de rendimiento

Conceptos aprendidos

Prueba con otro límite

`a, b = b, a % b`

`a * b // mcd(a, b)`

`from math import gcd`

`from functools import reduce`

`reduce(mcm, range(1, 21))`