March 15, 2026
Prime time, spicy takes
Generating All 32-Bit Primes (Part I)
Dev tries to list every 32‑bit prime — commenters shout “there’s a faster way”
TLDR: A dev generated every 32‑bit prime with a C program, but it took ~24 minutes. Commenters piled on with faster tools and tricks—Miller–Rabin on a phone, primesieve in seconds, and smarter sieves—sparking a DIY‑versus‑use‑the‑best‑tool debate that proves algorithm choice can be everything.
A lone coder set out to print every prime number that fits in a standard 32‑bit number, saving them to a file and double‑checking with a hash. The first pass used simple “try dividing” checks and clocked in around 24 minutes. Cue the crowd: the comment section arrived like a pit crew at a drag race.
Speed freaks flexed hard. One user bragged that the Miller–Rabin test (a fast, statistical check) “does them all in about three minutes on my phone,” linking a quick demo here. Another waved the flag for Kim Walisch’s primesieve, claiming 0.061 seconds, then cracked, “just use a bash indirection” to dump it to a file. Meanwhile, memory misers chimed in with the segmented sieve—“similar speed, way less RAM,” complete with a neat visual explorer. A math flex dropped a wild residue‑base trick using all 8‑bit primes. And the optimizer crowd pushed a hybrid “wheel + sieve” approach, with a handy Python example on Stack Overflow.
The vibe? A classic internet showdown: DIY craft vs. “use the best tool,” science project vs. speedrun. Jokes flew about “reinventing the wheel” and, yes, “reinventing the prime wheel.” Either way, the takeaway is clear: picking the right trick turns minutes into seconds.
Key Points
- •Goal: Generate all primes that fit in 32-bit uint32_t using a C program on Linux and write them to a binary PRIMES file in little-endian order.
- •A reference SHA-256 hash (272eb05aa040ba1cf37d94717998cbbae53cd669093c9fa4eb8a584295156e15) is provided to validate the output file.
- •Initial method uses trial division, testing divisibility by known primes up to √n, with careful overflow avoidance in p*p.
- •Complexity is analyzed as O(√n/ln n) per check and O(N√N/ln N) for generating all primes up to N; memory allocation targets 203,739,216 primes for 2^32−1.
- •The generated prime array is written with fwrite; the trial-division implementation ran in about 24m20s of user time on the author’s system. Wheel factorization is introduced for further optimization.