GoKawiilGenerating All 32-Bit Primes (Part I)
This article documents my quest to write a C program targeting Linux that generates all prime numbers that fit in a 32-bit unsigned int ( uint32_t ) as quickly as possible.
In particular, the program should write all 32-bit primes to a file (which, in all my implementations, is called PRIMES ) in binary, so that every 4 bytes of the file stores one primes number, with the bytes ordered in a little-endian fashion. In hex, the file should start out: 02 00 00 00 03 00 00 00 05 00 00 00 07 00 00 00 , and the correct SHA-256 hash for the file turns out to be: 272eb05aa040ba1cf37d94717998cbbae53cd669093c9fa4eb8a584295156e15 .
The algorithm used should able to correctly generate primes up to an arbitrarily large limit (within reasonable hardware constraints). It should not assume the primality of any number larger than 2 without first verifying it. It should not use a huge amount of memory—1GB should be plenty.
Trial Division
The simplest and most obvious way to check a number's primality is trial division. Given a target integer , where , we check if is divisible by each prime number less than or equal to its square root. If and only if it is not divisible by any of them, we can conclude that is prime. In C we could implement trial division like this:
/// Returns `true` iff `n` is a prime number. /// /// `primes`: an array of prime numbers in order, starting from 2, skipping /// none, and going at least up to the square root of `n`. bool is_prime(uint32_t n, uint32_t* primes) { for (size_t i=0; ; i++) { uint32_t p = primes[i]; if (n % p == 0) { return false; } // Comparison against 0xFFFF prevents overflow in `p*p` if (p >= 0xFFFF || p*p >= n) return true; } }
Trial division can be used to generate all the prime numbers up to a limit as follows: we create a growing list of the primes in order, which is initialized to {2} . Then we go through all the integers from to , checking the primality of each one and adding it to the end of the list if it is found to be prime. In C, for :
uint32_t* primes = (uint32_t*) malloc(203739216 * sizeof(uint32_t)); primes[0] = 2; size_t p_idx = 1; // index of the next element to be added to `primes` for (uint32_t n=3; n<=0xFFFFFFFF; n+=2) { if ( is_prime(n, primes) ) { primes[p_idx] = n; p_idx++; } // Prevents overflow in `n+=2` if (n == 0xFFFFFFFF) break; } [2]
This algorithm calls is_prime times, so its time complexity in the worst case is within .
... continue reading