Efficiently storing a list of prime numbers

Question

This article says:

Every prime number can be expressed as 30k±1, 30k±7, 30k±11, or 30k±13 for some k. That means we can use eight bits per thirty numbers to store all the primes; a million primes can be compressed to 33,334 bytes

---

"That means we can use eight bits per thirty numbers to store all the primes"

This "eight bits per thirty numbers" would be for k, correct? But each k value will not necessarily take-up just one bit. Shouldn't it be eight k values instead?

---

"a million primes can be compressed to 33,334 bytes"

I am not sure how this is true.

We need to indicate two things:

• VALUE of k (can be arbitrarily large)

• STATE from one of the eight states (-13,-11,-7,-1,1,7,11,13)

I am not following how "33,334 bytes" was arrived at, but I can say one thing: as the prime numbers become larger and larger in value, we will need more space to store the value of k.

How, then can we fix it at "33,334 bytes"?

Answer 1

The article is a bit misleading: we can't store 1 million primes, but we can store all primes below 1 million.

The value of k comes from its position in the list. We only need 1 bit for each of those 8 permutations (-13,-11..,11,13)

In other words, we'll use 8 bits to store for k=0, 8 to store for k=1, 8 to store for k=2, etc. By letting these follow sequentially, we don't need to specify the value of k for each 8 bits - it's simply the value for the previous 8 bits + 1.

Since 1,000,000 / 30 = 33,333 1/3, we can store 33,334 of these 8 bit sequences to represent which values below 1 million are prime, since we cover all of the values k can have without 30k-13 exceeding the limit of 1 million.

Answer 2

You don't need to store each value of k. If you want to store the prime numbers below 1 million, use 33,334 bytes - the first byte corresponds to k=0, the second to k=1 etc. Then, in each byte, use 1 bit to indicate "prime" or "composite" for 30k+1, 30k+7 etc.