Prime Number Table - Constant Seach Time
Posted on 2006-10-22
After a question with sunnycoder about searchtimes of sorted arrays, I've decided to try something out.
I want to be able to determine if a number is prime, a number between (1-10,000,000) in a constant period of time.
How I plan to do this is I'm going to make a list of prime numbers between 1-10,000,000 in an array.
So it would make sense to use an array with 10,000,000 boolean elements, but this is really overkill, since all i need is a single bit and not an 8bit boolean.
So what I was thinking was making an array of 10,000,000/32 elements, because each bit of the 32bit number can represent the boolean value for the number being prime. So for example, say I wanted to determine if the number 17 was prime, I would only need a single 32bit number, where the each bit was set corresponding to the number being prime or not so it would be something like: 0010101000101001010001000001010, does this make sense?
3 5 7 11 13 17 19 23 29 31
So since I know which bit in the number corresponds to 17 being prime or not, its rather trivial to determine whether or not 17 is prime.
The reason i'm doing it this way is just because I want to minimize the size of the array. Where with 8bit values i would have 10,000,000 bytes, by doing it like this the array size would become something like 10,000,000 / 8bits or around 1,250,000 bytes around (1mb vs 10mb).
I'm not really sure how to go about something like this. Figuring out if a number is prime seems pretty simple...
value = primeTable[(Number / 32)]
bitPosition = (Number % 32)
bitValue = ((Number << bitPosition) & 0x1) //right? Shift all the way to the right and bitwise and with 1???
The confusion I am having is about how to build this array, any suggestions would be appriciated.