Generating All 32-Bit Primes (Part I)

11 hours ago

The article describes a quest to write a C program targeting Linux that generates all 32-bit prime numbers as quickly as possible.
The program should write all primes to a binary file named PRIMES, with each prime stored as a 4-byte little-endian value.
The SHA-256 hash of the correct PRIMES file is provided for verification.
The algorithm must correctly generate primes up to an arbitrarily large limit without assuming primality and should use no more than 1GB of memory.
Trial division is the simplest primality test, checking divisibility by primes up to the square root of the number.
The time complexity of trial division is discussed, with worst-case performance analyzed.
Wheel factorization is introduced to skip checking numbers that are obviously not prime, such as even numbers or those divisible by small primes.
A wheel structure in C is defined to implement wheel factorization, improving efficiency by focusing only on potential primes.
The sieve of Eratosthenes is presented as a more efficient method, marking non-prime numbers in a bit array.
The sieve's time complexity is O(n log log n), significantly faster than trial division methods.
Performance comparisons show the sieve of Eratosthenes running in ~32s, much faster than trial division (~24m) or trial division with wheel factorization (~23m30s).
The article concludes with references to further optimizations and a GitHub repository containing the implementations.

Hasty Briefsbeta