This article says:
Every prime number can be expressed as
30k±1,30k±7,30k±11, or30k±13for somek. 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"?
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.