Someone else mentioned Miller-Rabin, and indeed if you have a limit on the bit width of your inputs then there is a fast deterministic test based on Miller-Rabin. Check out https://oeis.org/A014233
> a(12) > 2^64. Hence the primality of numbers < 2^64 can be determined by asserting strong pseudoprimality to all prime bases <= 37 (=prime(12)).
I don't know if this can get you down to sub-1-second like the primesieve project mentioned in the article, but still pretty cool to know.
susam 35 minutes ago [-]
I have a little tool called Prime Grid Explorer at https://susam.net/primegrid.html that I wrote for my own amusement. It can display all primes less than 3317044064679887385961981 (an 82-bit integer).
So essentially it can test all 81-bit integers and some 82-bit integers for primality. It does so using the Miller-Rabin primality test with prime bases derived from https://oeis.org/A014233 to determine whether a number is prime. The algorithm is implemented in about 80 lines of plain, vanilla JavaScript. If you view its source, look for the function named isPrimeByMR for the implementation.
senfiaj 4 hours ago [-]
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.
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
3 hours ago [-]
marxisttemp 3 hours ago [-]
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?
ZyanWu 4 hours ago [-]
> 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
logicallee 4 hours ago [-]
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.
for the way this one was done, this witness set has been proven to produce no false positives or negatives for n < 2³⁷.
_alternator_ 36 minutes ago [-]
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.
shablulman 4 hours ago [-]
[dead]
Rendered at 16:37:27 GMT+0000 (Coordinated Universal Time) with Vercel.
> a(12) > 2^64. Hence the primality of numbers < 2^64 can be determined by asserting strong pseudoprimality to all prime bases <= 37 (=prime(12)).
I don't know if this can get you down to sub-1-second like the primesieve project mentioned in the article, but still pretty cool to know.
The largest three primes it can show are
Direct link to the display: 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 the Miller-Rabin primality test with prime bases derived from https://oeis.org/A014233 to determine whether a number is prime. The algorithm is implemented in about 80 lines of plain, vanilla JavaScript. If you view its source, look for the function named isPrimeByMR for the implementation.
I use this algorithm here https://surenenfiajyan.github.io/prime-explorer/
64266330917908644872330635228106713310880186591609208114244758680898150367880703152525200743234420230
This would require 334 bits.
Does having the primes in a file even allow faster is-prime lookup of a number?
Oh, come on, just use a bash indirection and be done with it. It takes 1 minute and you had another result for comparison
[1] https://claude.ai/public/artifacts/baa198ed-5a17-4d04-8cef-7...