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
> 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
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?
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.
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/
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.
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
> 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
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?
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...