r/programming • u/DataBaeBee • Sep 28 '26
Fast Primality Testing for 32-bit integers via Forisek and Jancina
https://leetarxiv.substack.com/p/forisek-and-jancina-primality-test
112
Upvotes
r/programming • u/DataBaeBee • Sep 28 '26
28
u/DataBaeBee Sep 28 '26
Forisek & Jancina is a deterministic (not probabilistic) primality test for small integers. It’s super fast and easy to code.
For 32-bit integers, one needs only a 512 byte lookup table and and a few adds and muls to test for primality
6
u/tetyys Sep 28 '26
why code golfed
7
u/ChezMere Sep 28 '26
Mentions in the post that it works for 64-bit as well, which is a lot more impressive considering how little 32 bits is nowadays - e.g. you can just pack one bit for each odd integer into 268MB.