Primos 32 bits en C: criba óptima en 148 ms

¿Por qué generar todos los primos de 32 bits?

Hay 203.280.221 números primos entre 0 y 2^32 (4.294.967.295). Esa cifra puede parecer un detalle académico, pero para un ingeniero que construye tablas hash, filtros de Bloom, sistemas criptográficos o pipelines de datos, tener esa lista precalculada puede marcar la diferencia entre un servicio que responde en milisegundos y uno que se congela bajo carga. El artículo de hnlyman en GitHub Pages aborda exactamente ese problema: cómo generar todos esos primos en C de la forma más eficiente posible sobre Linux, comparando métodos clásicos con enfoques modernos y orientados a caché.

Los tres enfoques principales: de lo lento a lo rápido

1. División por prueba (Trial Division)

El método más intuitivo: para cada candidato n, se comprueba si es divisible por todos los impares hasta sqrt(n). Su complejidad temporal es O(N · sqrt(N)/2), lo que para N=2^32 se traduce en más de una hora de ejecución en hardware moderno. Es pedagógicamente valioso, pero inviable para producción a esta escala.

2. Factorización por rueda (Wheel Factorization)

La rueda módulo 30 (Wheel-30) aprovecha que todo primo mayor que 5 tiene la forma 30k ± 1, ± 7, ± 11 o ± 13. Esto descarta de entrada el 73% de los candidatos: múltiplos de 2, 3 y 5. El resultado es una reducción de entre 10 y 20 veces respecto a la división por prueba simple, bajando el tiempo a unos 5–10 minutos. Útil cuando la memoria es la restricción, ya que apenas consume 1 MB.

👥 ¿Quieres ir más allá de la noticia?

En nuestra comunidad discutimos las tendencias, compartimos oportunidades y nos ayudamos entre emprendedores. Sin humo, solo acción.

👥 Unirme a la comunidad

3. Criba de Eratóstenes segmentada y optimizada

Aquí está el salto de rendimiento real. La criba de Eratóstenes clásica tiene complejidad O(N log log N), pero su implementación ingenua para 2^32 requiere arrays enormes y destroza la caché de CPU. La versión optimizada combina varias técnicas:

Bitset compacto (1 bit por número, solo impares): reduce el consumo de memoria a ~536 MB frente a los ~4 GB de un array de booleanos.
Segmentación en bloques de 1 MB: alineada con la caché L2/L3 del procesador, evitando penalizaciones por cache miss.
Pre-filtrado con Wheel-30: combina lo mejor de ambos mundos, saltando candidatos triviales antes de aplicar la criba.
Compilación con -O3 -march=native -mbmi2 en GCC/Clang para aprovechar instrucciones AVX en el marcado de compuestos.

El resultado: generación y escritura en disco de los 203 millones de primos en aproximadamente 148 ms (incluyendo I/O) en un Intel i7 de gama media bajo Linux x86_64. El tiempo de cómputo puro ronda los 100 ms.

Comparativa de rendimiento

Algoritmo	Tiempo aprox. (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

Como referencia, primesieve —la librería C/C++ considerada estado del arte en generación de primos, mantenida por Kim Walisch en GitHub y capaz de trabajar hasta 10^19— tarda aproximadamente 200 ms para la misma tarea. El enfoque del artículo supera a primesieve en el rango específico de 32 bits gracias a las optimizaciones de bajo nivel.

Aplicaciones prácticas para founders e ingenieros

Más allá del ejercicio teórico, tener una lista precalculada de primos de 32 bits abre posibilidades concretas:

Tablas hash y estructuras probabilísticas: elegir tamaños primos reduce colisiones en tablas hash y mejora la distribución en filtros de Bloom, clave en motores de búsqueda y sistemas de deduplicación.
Criptografía y seguridad: generación de claves RSA y Diffie-Hellman donde se necesita seleccionar aleatoriamente un primo de un rango dado; contar con la lista en disco acelera el proceso eliminando pruebas de primalidad en caliente.
Simulaciones y pipelines de datos: algoritmos que requieren números con propiedades aritméticas específicas (p. ej., semillas para generadores pseudoaleatorios) se benefician de acceso O(1) a un primo arbitrario.
Prototipado de librerías matemáticas: base para implementar la prueba de Miller-Rabin determinista sobre todos los enteros de 32 bits, con witnesses fijos y sin aleatoriedad.

Herramientas y referencias del ecosistema

Si este tema te resulta relevante para tu stack o producto, aquí hay recursos complementarios:

primesieve (kimwalisch/primesieve): librería C/C++ con bindings para Python, Ruby y más. Ideal para rangos superiores a 2^32.
Segmented Sieve en DEV Community (totally_chase): implementación en C puro con foco en récords de velocidad y buenas prácticas de caché.
Wikipedia — Generation of Primes: visión general de todos los algoritmos conocidos con referencias a papers formales.
GeeksforGeeks — Large Prime Generation for RSA: guía práctica para integrar generación de primos en flujos criptográficos.

Consideraciones de hardware y sistema operativo

El artículo está pensado específicamente para Linux x86_64. Las optimizaciones que más impactan son:

mmap para asignación de grandes arrays sin fragmentación del heap.
posix_fadvise con POSIX_FADV_SEQUENTIAL para escritura eficiente en disco.
Compilación con soporte BMI2 (Bit Manipulation Instructions) para operaciones de bits ultrarrápidas sobre el bitset.

En sistemas con menos de 512 MB de RAM disponible, la variante Wheel-30 sin criba completa sigue siendo una opción viable con un coste de tiempo asumible para rangos parciales.

Conclusión

Generar todos los primos de 32 bits en menos de 150 ms no es solo un ejercicio de optimización académica: es un ejemplo concreto de cómo la elección de algoritmo correcto, combinada con conocimiento de hardware (caché, instrucciones SIMD, I/O eficiente), puede transformar una tarea que tomaría horas en algo que sucede en un parpadeo. Para founders e ingenieros que construyen productos sobre infraestructura propia, este tipo de razonamiento —medir, comparar, optimizar por capas— es exactamente la mentalidad que diferencia un sistema que escala de uno que colapsa. Si trabajas en criptografía, almacenamiento, búsqueda o cualquier dominio donde la aritmética de números importa, vale la pena tener este toolbox en la cabeza.

Descubre cómo otros founders implementan estas soluciones de optimización y rendimiento en sus productos reales.

Ver con founders