What is the maximum number of primes that I can pack in a 30KB text file? If I store in trivial way I can store roughly 5100 primes ie primes upto 50k in a 30KB file.
Actually I need primes till $2^{30}$ but obviously its not possible to store such a huge list in a file of size of the order of some KBs. So my goal is the store as many primes as possible in a 30KB file. And then retrieve them in sublinear computation time. And beyond that limit I will have to sieve anyways.
I have gone though this answer but doesnt quite fully satisfy me, So it would be great if someone can get the max compressed list with implementation of packing/unpacking algorithm.
I can afford to go for a retrieval/unpacking algo wchich is more than $O(1)$  per prime but has to be definitely sublinear ie less than $O(N)$ where N is size of list.
 A: The simplest solution is to store a bitmask of which numbers are prime. This takes 1 bit per integer, which is enough to determine primality for all numbers up to roughly 2^18.
It is however, possible to do much better than this by not storing multiples of 2, 3, or 5. This will increase the size of the code a little bit, but will let you store 3.75x more data (or roughly up to 900,000).
This still isn't optimal since only roughly 1/3rd of these bits are 1s, which implies this data could be further compressed, but this is approaching the limit. I would be very surprised if it's possible to store anything more than the primes up to 2,000,000 or so.
A: As a compromise between speed and compression, I'd put 30 primes/byte by marking primes as 30k+(1,7,11,11,13,17,23,29). This would give primes to about 112,000.
You can get better by using numbers using the "wheel numbers": 210, 2310, 30300, etc.
At some point (I don't know where), one can store the differences from the current prime to the next. Maybe a universal code would help here. I don't know if a universal code would be good in making a prime list.
A: I'm assuming the interface you want is to be able to retrieve the $n$th prime given $n$.
The simplest way would be to store an array of primes, three bytes per prime. That's $30 \cdot 1024 / 3 = 10240$ primes that can fit into 30KB.

One very simple improvement is to group the array into blocks of 12 primes
$$\boxed{\color{red}{2}, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}, \boxed{\color{red}{41}, 43, 47, \cdots}$$
The first prime in each block, the base, is stored in three bytes. The rest of the primes in the block are stored as a difference from the base in one byte. The block size of 12 was chosen empirically to make the differences fit.
That's 12 primes in 3+11=14 bytes, or $30\cdot 1024 \cdot (12/14) \approx 26330$ primes that fit in 30KB.

Another slight improvement: by removing 2 from the list, all the remaining primes are odd, so the differences from the base will all be even. So instead of storing the difference, we can store half the difference. Now differences of up to 510 will fit in one byte, so we can increase the block size up to 29.
29 primes in 3+28=31 bytes, or $30\cdot 1024 \cdot (29/31) \approx 28730$ primes that fit in 30KB.
Here's a small Python script demonstrating the packing/retrieval code for this.
