title: Efficient storage of prime numbers
body: <p>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).</p>
  
  <p>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.</p>
  
  <p>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)</p>
  
  <p>(the language I wrote this in is <a href="http://www.factorcode.org/" rel="noreferrer">Factor</a> but this question would be the same in any language which has built-in or easily programmable packed bit arrays)</p>