203 millones de números primos. Generarlos todos —cada primo que cabe en un entero de 32 bits— puede tomarte más de una hora o 148 milisegundos. La diferencia no es hardware nuevo ni una GPU de última generación: es elegir el algoritmo correcto y diseñarlo para que hable el mismo idioma que la caché del procesador.
Eso es exactamente lo que documenta el ingeniero hnlyman en un artículo técnico que compara tres aproximaciones clásicas al problema. La historia es un caso de estudio comprimido sobre algo que cualquier dev debería tener grabado: el algoritmo no vive en el vacío, vive en hardware concreto.
¿Por qué importa tener todos los primos de 32 bits?
El rango de uint32_t va de 0 a 4.294.967.295. Dentro de ese espacio viven exactamente 203.280.221 números primos. Para la mayoría de aplicaciones, ese número es trivia. Para quien construye tablas hash de alta performance, filtros de Bloom, sistemas criptográficos (generación de claves RSA o Diffie-Hellman), o pipelines de datos que dependen de propiedades aritméticas específicas, tener esa lista precalculada puede ser la diferencia entre un servicio que responde en microsegundos y uno que bloquea bajo carga.
Claude Desbloqueado
Mi curso avanzado para aprender a sacarle mucho más provecho a Claude en el trabajo y en el día a día, con funciones y usos más potentes. Comienza el 23 de marzo.
→ Inscríbete hoy 🚀El problema concreto: generar todos esos primos en C, escribirlos a disco en binario, con la menor memoria posible y en el menor tiempo.
Tres algoritmos, tres órdenes de magnitud
División por prueba (Trial Division): el método más intuitivo. Para cada candidato n, se verifica si es divisible por todos los impares hasta √n. Complejidad: O(N · √N/2). Para N=2³², esto se traduce en más de una hora de ejecución en un i7 moderno. Pedagógicamente útil, inviable en producción.
Factorización por rueda (Wheel-30): una optimización elegante basada en observar que todo primo mayor que 5 es de la forma 30k ± {1, 7, 11, 13}. Esto descarta de entrada el 73% de los candidatos (múltiplos de 2, 3 y 5). El tiempo baja a 5–10 minutos. Consume menos de 1 MB de RAM, útil cuando la memoria es la restricción.
Criba de Eratóstenes segmentada y optimizada: aquí ocurre el salto de tres órdenes de magnitud. La criba clásica ya tiene complejidad O(N log log N), pero su implementación ingenua para 2³² requiere arrays enormes y destroza la caché. La versión optimizada apila cuatro técnicas:
- Bitset compacto: 1 bit por número (solo impares), lo que reduce la huella de memoria de ~4 GB a ~536 MB.
- Segmentación en bloques de 1 MB: alineada con la caché L2/L3 del procesador. Cada segmento cabe completo en caché, eliminando los costosos cache miss que paralizaban la versión ingenua.
- Pre-filtrado Wheel-30: combina ambas optimizaciones, descartando múltiplos triviales antes de entrar a la criba.
- Compilación -O3 -march=native -mbmi2: aprovecha instrucciones AVX y BMI2 para las operaciones de bits, junto con
mmapyposix_fadvisepara I/O eficiente sin fragmentar el heap.
Resultado: 148 ms totales (incluyendo escritura a disco). Cómputo puro: ~100 ms. Esto supera a primesieve, la librería C/C++ considerada estado del arte en generación de primos, que en el mismo rango tarda ~200 ms.
La lección que va más allá del benchmark
El salto de una hora a 148 ms no viene de un solo truco. Viene de pensar en capas: primero el algoritmo (criba vs. división), luego la estructura de datos (bitset vs. array de bytes), luego el comportamiento en caché (segmentación), luego las instrucciones del hardware (SIMD).
Este tipo de razonamiento estratificado tiene aplicación directa más allá de primos. La misma secuencia —medir, identificar el cuello de botella real, resolver capa por capa— es lo que separa un sistema que escala de uno que colapsa bajo carga. Si construyes herramientas de búsqueda, motor de recomendaciones, o cualquier pipeline donde la aritmética importa, la pregunta no es “¿qué tan rápido es mi CPU?” sino “¿en qué nivel está el cuello de botella: algoritmo, memoria, caché, I/O?”
Vale la pena contrastar esto con el debate actual sobre código generado por IA. Herramientas como Claude Code son excelentes para generar implementaciones correctas, pero el razonamiento sobre qué algoritmo elegir y por qué —basado en las características del hardware— sigue siendo territorio donde la comprensión profunda del dev marca la diferencia. Y como señala la investigación sobre código generado por IA, pasar los tests no equivale a tener código que se comporte bien en producción bajo condiciones de carga real.
Tabla de referencia
| Algoritmo | Tiempo (i7, Linux) | Memoria |
|---|---|---|
| División por prueba | >1 hora | <1 MB |
| Wheel-30 Trial | 5–10 min | <1 MB |
| Criba básica (bit-packed) | 2–5 seg | ~512 MB |
| Criba segmentada optimizada | ~148 ms | ~536 MB |
| primesieve (estado del arte) | ~200 ms | ~536 MB |
El código completo y las variantes documentadas están en el artículo original de hnlyman. Para rangos mayores que 2³², la librería primesieve de Kim Walisch soporta hasta 10¹⁹ con bindings para Python, Ruby y otros lenguajes.
