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

▲

tromp 5 hours ago | parent [-]

Or a C implementation at https://tromp.github.io/pearls.html#sieve which runs in well under 10s.

▲

hnlyman 4 hours ago | parent [-]

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.

	▲	tromp an hour ago \| parent [-]
		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.