Generar todos los números primos que caben en 32 bits suena a obsesión de programador, pero en realidad es una buena clase de ingeniería de rendimiento. No porque alguien necesite tener 203.280.221 primos en la cabeza, sino porque el camino para calcularlos rápido muestra algo que sigue siendo verdad en 2026: elegir bien el algoritmo y respetar la caché del procesador puede valer más que tirar fuerza bruta al problema.
Ese es el valor real detrás de la discusión que abrió Henry Lyman al intentar escribir en C, para Linux, un programa capaz de generar todos los primos de 32 bits y guardarlos en un archivo binario. La pregunta no es solo “¿se puede?”. La pregunta útil es otra: ¿qué cambia cuando dejas de pensar en matemáticas abstractas y empiezas a pensar en memoria, segmentación y acceso al disco?
¿Qué problema está intentando resolver realmente?
Entre 0 y 232 hay exactamente 203.280.221 números primos. Tenerlos precalculados no es una curiosidad vacía: sirve para elegir tamaños de tablas hash, alimentar filtros de Bloom, acelerar ciertos flujos criptográficos o probar librerías numéricas sin recalcular primalidad cada vez. En otras palabras, es una tarea extrema, pero toca varios problemas muy reales de infraestructura.
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 🚀Lo interesante es que la versión ingenua del problema se hunde rápido. Si intentas decidir la primalidad de cada número con división por prueba, el costo crece demasiado. En la implementación base de Lyman, ese enfoque tarda cerca de 24 minutos y 20 segundos para cubrir todo el rango. Funciona, sí, pero ya te muestra el límite de pensar el problema “número por número”.
La lección clave no es matemática: es arquitectura
La mejora obvia es saltarte candidatos imposibles. Ahí entra la wheel factorization, una técnica que elimina desde el principio múltiplos de primos pequeños como 2, 3 y 5. Sobre el papel suena prometedora, porque reduce bastante el universo de números a revisar. En la práctica, la mejora no fue dramática: el tiempo baja apenas a unos 23 minutos y 30 segundos.
Eso importa porque desmonta una intuición muy común: no basta con “hacer menos operaciones”. También importa qué operaciones haces y cómo golpean la memoria. Saltarte candidatos ayuda, pero si sigues pensando el problema como una secuencia enorme de comprobaciones individuales, no cambias el cuello de botella principal.
El salto real llega con la criba de Eratóstenes. En vez de preguntar “¿este número es primo?”, la criba cambia de enfoque y marca los compuestos de forma sistemática. Esa diferencia de modelo es la que convierte una tarea larguísima en una tarea razonable. En la implementación descrita por Lyman, la criba baja el tiempo a unos 32 segundos.
¿Por qué la criba gana por tanto margen?
Porque deja de tratar cada número como un caso aislado. Y porque permite optimizaciones mucho más cercanas al hardware:
- Bitsets en vez de booleanos: guardar un bit por número reduce de golpe el uso de memoria frente a un arreglo ingenuo.
- Accesos más previsibles: marcar múltiplos en bloques ordenados es mucho más amable con la caché de CPU que hacer divisiones repetidas y saltos irregulares.
- Segmentación: partir el problema en tramos permite que las estructuras activas vivan más tiempo dentro de caché L1/L2, donde todo ocurre mucho más rápido.
Ese punto conecta muy bien con otras historias “bajo el capó” que ya hemos visto en descubre.ai. Cuando explicamos cómo RegisterForge convierte datasheets de chips en código, el patrón era parecido: el rendimiento no sale de magia, sale de modelar bien el problema y reducir el trabajo inútil. Acá pasa lo mismo, pero en clave matemática.
¿Dónde entra primesieve en esta conversación?
Acá conviene no vender humo. La fuente original que revisamos no sostiene por sí sola el titular secundario de “148 ms” que circula en la nota resumida. Lo que sí sostiene con claridad es otra cosa: todavía hay bastante margen sobre esos 32 segundos si usas una implementación estado del arte.
El ejemplo más claro es primesieve, la librería de Kim Walisch. Su documentación explica que combina criba segmentada, wheel factorization y optimizaciones centradas en caché para reducir misses de memoria y mantener el trabajo dentro de segmentos pequeños. También usa arreglos de bits, pre-sieving y distintas estrategias según el tamaño de los primos usados para cribar. En el propio artículo de Lyman aparece un dato útil como referencia: primesieve puede generar todos los primos de 32 bits en alrededor de 0,061 segundos, aunque sin el costo de escribirlos al archivo final.
Eso deja una idea importante para cualquier dev: la discusión no es “C vs no C”. La discusión real es si tu implementación está alineada con cómo funciona el hardware. Si no lo está, puedes perder dos órdenes de magnitud aunque el algoritmo “correcto” esté sobre la mesa.
Por qué importa
Este tema no va a cambiar la vida del lector promedio, pero sí le dice algo muy útil a cualquiera que construya software: hay problemas donde la optimización de verdad no nace en el microbenchmark bonito, sino en entender dónde estás perdiendo memoria, caché y ancho de banda. Por eso piezas aparentemente de nicho siguen siendo valiosas. Igual que vimos con Han, el lenguaje de programación en coreano que desafía el inglés, las decisiones de diseño aparentemente pequeñas terminan definiendo quién puede usar una tecnología y con qué costo.
En este caso, la enseñanza es cristalina: si un problema parece demasiado grande, no siempre necesitas más máquina. A veces necesitas cambiar la forma de pensarlo. Pasar de división por prueba a criba segmentada no es una mejora cosmética. Es cambiar una mentalidad artesanal por una mentalidad de sistemas.
