Jonathan. Frech’s WebBlog

Prime Intirety (#206)

Jonathan Frech,

Since an­cient times humanity knew that there are infinitely many primes — though countable, writ­ing a com­plete list of every prime is im­pos­si­ble if one intends to finish.
How­ev­er, in practice one often on­ly considers a minute subset of the naturals to work with and think about. When writ­ing low-level languages like C, one is nearly forced to forget about almost every natural num­ber — the data type u_int_32, for example, is on­ly ca­pa­ble of representing $\{\mathbb{N}_0\ni n<2^{32}\}$$\{\mathbb{N}_0\ni n<2^{32}\}$$\{\mathbb{N}_0\ni n<2^{32}\}$.
Therefore, it is possible to produce a com­plete list of every prime representable in thirty-two bits using stan­dard bit pattern in­ter­pre­ta­tion — the entirety of the first 203 280 221 primes.

Gen­er­ating said list took about two minutes on a 4GHz Intel Core i7 using an elementary sieve ap­proach writ­ten in C com­piled with gcc -O2.
All primes are stored in little-endian format and packed densely to­geth­er, requiring four bytes each.

Using the resulting file, one can quickly index the primes, for example $p_{10^7}=179\,424\,691 = \text{ab1cdb3}_{16}$$p_{10^7}=179\,424\,691 = \text{ab1cdb3}_{16}$$p_{10^7}=179\,424\,691 = \text{ab1cdb3}_{16}$ (using zero-based indexing). Since each prime is stored using four bytes, the prime’s index is scaled by a fac­tor of four, resulting in its byte index.

dd status=none ibs=1 count=4 if=primes.bin skip=40000000 | xxd 
00000000: b3cd b10a                                ....

Source code: prime-intirety.c
Prime list (gzipped and split): ((a directory))