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.
IMO that algorithm is barely a sieve. It is technically pareto optimal, but it seems like in practice it would just end up worse than either an optimized segmented sieve (it is ~log(n)^2 slower) or an O(1) memory method (probable prime test followed by a deterministic prime test) depending on how large and how wide the numbers you're testing are.
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
I'd be interested in seeing an explanation of the code, since it looks pretty incomprehensible to me. Per the arbitrary rules I set for myself, I'm not allowed to precompute/hardcode the wheel (looks like this implementation uses a hardcoded wheel of size 2x3x5=30). I wonder if/by how much the performance would suffer by computing and storing the coprime remainders in memory instead of handing them directly to the compiler.
I wrote this in a semi obfuscated style to make it fit on one screen.
It's indeed a hardcoded 2x3x5 wheel; but I suspect computing all those
constants would have made the program significantly longer.
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?
This got me through many of the first 100 problems on Project Euler:
n = 1000000 # must be even
sieve = [True] * (n/2)
for i in range(3,int(n**0.5)+1,2):
if sieve[i/2]: sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
…
# x is prime if x%2 and sieve[x/2]
Edit: I guess I irked someone. :/ Yes this is a memory hog, but to me beautiful because it’s so tiny and simple. I never tried very hard, but I wonder if it could be made a real one-liner.
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.
Heh.
1.Create fast modulus quad M for dword D for the first 2000? 200000? (xM)D
2.Eliminate 0b,101b
3.Divide using vrcp14ss/vdivss with correction. Use fast square root too using rsqrt14.
> 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
28 comments
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?
[1] https://claude.ai/public/artifacts/baa198ed-5a17-4d04-8cef-7...
> 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