Este artículo explora la generación de todos los números primos de 32 bits (uint32_t) en Linux de la manera más rápida posible. El objetivo es crear un programa en C que escriba estos primos en un archivo binario, con cada número primo representado en 4 bytes en formato little-endian. El archivo resultante debe tener un hash SHA-256 específico. El enfoque principal es la implementación del algoritmo de división de prueba (trial division), que verifica la primaciedad de un número dividiéndolo por todos los primos menores o iguales a su raíz cuadrada. Aunque simple, esta técnica tiene una complejidad temporal considerable, especialmente para números grandes.
El artículo detalla cómo optimizar este proceso. Inicialmente, se crea una lista creciente de primos, comenzando con 2, y se verifica la primaciedad de cada número entero desde 3 hasta el máximo valor de uint32_t (0xFFFFFFFF). Se aprovecha el hecho de que todos los números pares mayores que 2 no son primos, incrementando el bucle de verificación en 2. Además, se introduce la optimización basada en la congruencia de los primos: todos los primos mayores que 3 son congruentes con 1 o 5 módulo 6. Esto permite eliminar rápidamente candidatos no primos.
Una mejora significativa se logra mediante el uso de una 'rueda' (wheel). Esta técnica se basa en la observación de que los primos mayores que 5 son congruentes con 1, 7, 11, 13, 17, 19, 23 o 29 módulo 30. La rueda representa estas congruencias, permitiendo verificar la primaciedad solo de los números que cumplen con estas condiciones, reduciendo significativamente el número de divisiones necesarias. La implementación con una rueda basada en los primeros 5 primos ofrece una ligera mejora en el tiempo de ejecución.
El artículo también aborda consideraciones prácticas como la prevención de desbordamientos de enteros durante los cálculos y la gestión de la memoria. La implementación final, disponible en código fuente, tardó aproximadamente 24 minutos en ejecutarse en el sistema del autor, mientras que la versión con rueda tardó alrededor de 23 minutos y medio. La optimización de algoritmos de generación de primos es un problema complejo con implicaciones en diversas áreas, como la criptografía y la informática teórica.