April 10, 2026
Prime drama: 4GB sieves vs smart tests
Deterministic Primality Testing for Limited Bit Width
Four tiny checks, huge fight: how devs spot primes
TLDR: A blog shows a simple way to check 32‑bit numbers for primes using four tiny test values that guarantees the right answer. Commenters split into camps: sieve lovers hauling 4GB files, fans of a hybrid Baillie–PSW check, and minimalists who want fewer checks—with jokes about factoring odometers.
A calm blog post about a simple, always-correct way to spot prime numbers in 32‑bit land—using four tiny checks (2, 3, 5, 7)—turned into a full-on comment brawl. The code promises a deterministic result, meaning no guessing, and links to OEIS A014233 for the math receipts. But the community didn’t show up for quiet math; they came for the showdown.
One camp flexed raw power: one user bragged they ditched fancy tests and generated a 4GB file of primes with the classic “sieve” method—because why be subtle when you can be certain. The optimization nerds fired back: another commenter said you can do the same 32‑bit job with even fewer checks, citing better-known base sets and deep links to Miller–Rabin lore. Then came the curveball: a claim that the Baillie–PSW hybrid test is good for everything under 64‑bit numbers, sparking the “use the right tool!” chorus—sieve for finding all primes in a range, lighter tests for one-off checks.
Meanwhile, a delightful side quest: someone confessed they try to factor their car’s odometer in their head to stay sharp, turning the thread into math-gym humor. Between chest-thumping about speed, debates over minimal magic numbers, and brainy party tricks, the real message was clear: the code is neat, but the community is very opinionated about how to hunt primes—and they brought jokes, receipts, and a little chaos.
Key Points
- •The article presents a deterministic primality test for 32-bit integers using Miller–Rabin with fixed bases {2, 3, 5, 7}.
- •OEIS A014233 is cited to justify that these bases ensure determinism for all 32-bit inputs.
- •The C++ implementation uses 64-bit intermediates to avoid overflow while assuming 32-bit input values.
- •Algorithm steps include early trivial checks, factoring n−1 as 2^s·d via trailing zeros, modular exponentiation, and squaring rounds per base.
- •Historical context references the Miller–Rabin randomized test and notes a 2002 result by Agrawal, Kayal, and Saxena in deterministic primality testing.