Inicio · Parte 04 — Matemática discreta para computación
criba: tachar múltiplos desde i² con i ≤ √n
mcd(a,b)·mcm(a,b) = a·b
Euclides: mcd(a,b) = mcd(b, a mod b)La criba de Eratóstenes, del siglo III a.C., sigue siendo el método práctico para listar todos los primos hasta n. Su eficiencia viene de dos optimizaciones: basta recorrer hasta √n, porque todo compuesto tiene un factor menor o igual a su raíz; y basta empezar a tachar desde i², porque los múltiplos menores ya fueron tachados por primos anteriores. El coste es O(n log log n), prácticamente lineal.
El algoritmo de Euclides para el máximo común divisor es aún más antiguo y es un candidato al algoritmo no trivial más antiguo que se sigue usando. Su idea —mcd(a,b) = mcd(b, a mod b)— reduce el problema en cada paso y termina en O(log min(a,b)).
La identidad mcd·mcm = a·b permite calcular el mínimo común múltiplo sin factorizar, que es importante porque factorizar es difícil mientras que calcular el mcd es fácil. Esa asimetría es la que sostiene RSA: multiplicar dos primos grandes es inmediato, recuperarlos del producto no se sabe hacer eficientemente.
El teorema fundamental de la aritmética —toda factorización en primos es única— es lo que da sentido a todo esto. Y el hecho de que los primos sean infinitos, demostrado por Euclides con un argumento por contradicción de tres líneas, garantiza que siempre hay primos suficientemente grandes para la criptografía.
Criba hasta 50 y mcd de dos números.
Primos ≤ 50 (15 en total):
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
mcd(252, 198) por Euclides:
252 = 1·198 + 54
198 = 3·54 + 36
54 = 1·36 + 18
36 = 2·18 + 0 → mcd = 18
mcm = 252·198/18 = 2772
Verificación: 18 · 2772 = 49 896 = 252 · 198 ✓
Factorización de 252 = 2²·3²·7Criba, MCD por Euclides y su relación con el mínimo común múltiplo.
python classes/part-04-matematica-discreta-para-computacion/099-numeros-primos-y-maximo-comun-divisor/lab.py
compmath run 099primos_hasta_50cantidadabmcdmcmmcd*mcm=a*bfactorizacion_de_252{
"primos_hasta_50": [
2,
3,
5,
7,
11,
13,
17,
19,
23,
29,
31,
37,
41,
43,
47
],
"cantidad": 15,
"a": 252,
"b": 198,
"mcd": 18,
"mcm": 2772
}Generación de claves criptográficas, simplificación de fracciones, tests de primalidad y hashing con módulos primos.
Los grafos de cómputo, la búsqueda en árbol y las GNN son estructuras discretas; el conteo sostiene la probabilidad que después usa todo modelo generativo.
9780199219865 verificado en International ISBN Agency (2026-08-19).math.gcd y math.lcm — documentación de la herramienta que ejecuta el laboratorio · URL de la fuente primaria comprobada en Python Software Foundation (2026-08-19).