View Single Post
Old 2019-05-10, 02:55   #9
axn's Avatar
Jun 2003

19·271 Posts

Originally Posted by hansl View Post
Could you explain how you got to that estimate? What exactly is being stored in this case?
There are 8 modular classes that don't have trivial factors (mod 30). These are {1,7,11,13,17,19,23,29}. So you use 8 bitmaps each of length 2^32/30 bits. The first bitmap will store all numbers of the form 1+30n -- bit 0 will be 1, bit 1 will be 31, bit 2 will be 61, etc..
Second bitmap will store 7+30n, and so on.

Total size for all these bitmaps would be (2^32/30)*8 bits or 2^32/30 byte which is about 136.5 MB.

To see if a number k > 5 and < 2^32 is prime, decompose k into
q = floor(k/30), r=k%30
if r is not one of {1,7,11,13,17,19,23,29}, it is not prime.
Else lookup qth bit from the appropriate bitmap.
axn is online now   Reply With Quote