Efficiently storing a list of prime numbers
- by eSKay
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?
