Efficient storage of prime numbers
For a library, I need to store the first primes numbers up to a limit L. This collection must have a O(1) lookup time (to check whether a number is prime or not) and it must be easy, given a number, to find the next prime number (assuming it is smaller than L).
Given that L is fixed, an Eratostene sieve to generate the list is fine. Right now, I use a packed boolean array to store the list, which contains only entries for odd numbers between 3 and L (inclusive). This takes (L-2)/2 bits of memory. I would like to be able to statically increase L without using more memory.
Is there a data structure using less memory with similar properties? Or with at least the constant lookup time? (odd numbers can then be enumerated until we get a prime)
(the language I wrote this in is Factor but this question would be the same in any language which has built-in or easily programmable packed bit arrays)
Answer
You can explicitly check more prime numbers to remove redundancy.
At the moment you do this only for two, by checking for divisibility by two explicitly and then storing only for odd numbers whether they are prime.
For 2 and 3 you get remainders 0 to 5, of which only 1 and 5 are not divisible by two or three and can lead to a prime number, so you are down to 1/3.
For 2, 3, and 5 you get 8 numbers out of 30, which is nice to store in a byte.
This is explained in more detail here.