Hacker News new | past | comments | ask | show | jobs | submit

Generating All 32-Bit Primes (Part I)

https://hnlyman.github.io/pages/prime32_I.html
57hnlyman | | 17 | HN
susam | parent | next
My little Prime Grid tool at <https://susam.net/primegrid.html> can display all primes less than 3317044064679887385961981 (an 82-bit number).

The largest three primes it can show are

  3317044064679887385961783
  3317044064679887385961801
  3317044064679887385961813
Here is a direct link to it: <https://susam.net/primegrid.html#3317044064679887385961781-2...>.

So, essentially it can test all 81-bit integers and some 82-bit integers for primality. It does so using Miller-Rabin primality test with prime bases drawn from https://oeis.org/A014233 to determine whether a number is prime.

Here is the complete implementation of the algorithm: <https://github.com/susam/susam.net/blob/0.6.0/content/tree/p...>

senfiaj | parent | next
There is also the segmented Sieve of Eratosthenes. It has a simlar performance but uses much less memory: the number of prime numbers from 2 to sqrt(n). For example, for n = 1000000, the RAM has to store only 168 additional numbers.

I use this algorithm here https://surenenfiajyan.github.io/prime-explorer/

loading story #47389077
loading story #47389020
forinti | parent | next
If you take all 53 8 bit primes, you can use modular arithmetic with a residue base to work with numbers up to

64266330917908644872330635228106713310880186591609208114244758680898150367880703152525200743234420230

This would require 334 bits.

mark-r | parent | next
You can combine the Sieve and Wheel techniques to reduce the memory requirements dramatically. There's no need to use a bit for numbers that you already know can't be prime. You can find a Python implementation at https://stackoverflow.com/a/62919243/5987
loading story #47389679
| parent | next
{"deleted":true,"id":47387218,"parent":47386441,"time":1773581509,"type":"comment"}
ZyanWu | parent | next
> There is a long way to go from here. Kim Walisch's primesieve can generate all 32-bit primes in 0.061s (though this is without writing them to a file)

Oh, come on, just use a bash indirection and be done with it. It takes 1 minute and you had another result for comparison

marxisttemp | parent | next
Why include writing the primes to a file instead of, say, standard output? That increases the optimization space drastically and the IO will eclipse all the careful bitwise math

Does having the primes in a file even allow faster is-prime lookup of a number?

logicallee | parent | next
there are also very fast primality tests that work statistically. It's called Miller-Rabin, I tested in the browser here[1] and it can do them all in about three minutes on my phone.

[1] https://claude.ai/public/artifacts/baa198ed-5a17-4d04-8cef-7...

amelius | parent
What are the false positive/negative rates?
logicallee | root | parent
for the way this one was done, this witness set has been proven to produce no false positives or negatives for n < 2³⁷.
_alternator_ | root | parent
Nice. Notably with Miller-Rabin, you can also iterate the test cheaply and get exponentially low false positive/negative rates. I believe that this is how prime factors for RSA keys are usually chosen; choose an error rate below 2^-1000 and sleep extremely soundly knowing that the universe is more likely to evaporate in the next second than that you’ve got a false positive prime.