Comment by mark-r
10 hours ago
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
Or a C implementation at https://tromp.github.io/pearls.html#sieve which runs in well under 10s.
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.