Quote:
Originally Posted by hansl
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.