How to shorten prime numbers in database? I'm bad at Math and english isn't my native language. Bear with me. Thanks.
I'm running a prime number search script and writing the result to a SQLite3 database.
Now I'm looking for a way to shorten these prime numbers because I don't want to be forced to store them as strings if they get very big/long. I don't want to loose precision, so the shortened version should allow it to recompute the original value.
I don't care if the database has human-readable data. I can make it human-readable when I fetch data from the database again.
Browsed https://oeis.org and https://primes.utm.edu to see how they organize their database, but I was only more confused after that. Is there a best practice for this? I'm really stuck.
 A: You could try to save the database in binary format I guess. Otherwise each numeral in a number has fixed size of presumably 1-byte, whereas even without improvements you could store numbers up to 256 in 1-byte in binary format.
Also you may wanna check Huffman coding but I doubt it would help in a prime case.
A: Let's consider how much compression you can get by clever encoding
of your primes to reduce the amount of memory or file space
each one occupies.
Whatever encoding you choose, I assume you want it to work for any prime,
so that no matter which prime you encode by this method, you can
recover the original prime from the encoding later.
Suppose you had a function that could tell you the $n$th largest prime quickly enough so that you could just encode the $n$ largest prime
as the number $n$ and store it in that format.
That's the densest possible encoding that you could have.
Assuming you stored the number in decimal format,
in order to store primes larger than $15\,485\,863$
(the millionth prime) you would need to use seven digits for some
of the primes.
That is, by this incredibly efficient compression scheme you would
be able to store eight- or nine-digit numbers such as $15\,485\,867$
or $179\,424\,673$ in just seven digits.
In order to store primes larger than $179\,424\,673$
(the ten millionth prime) you would need to use eight digits,
and this would allow you to store nine-digit primes 
and some ten-digit primes.
In general, in order to encode a prime with numeric value $N$
in this fashion, the encoding itself will be about $N/\ln(N).$
That means to encode a prime with twelve decimal digits the encoding will
be about $10^{11}/\ln(10^{11}) \approx 3.9\times10^9$ at least--that is,
ten digits or more.
The encoding for a large twelve-digit prime would be closer to
$10^{11}/\ln(10^{11}) \approx 3.6\times10^{10},$ which has eleven digits.
To encode primes of up to twenty digits using this scheme, most of the
numbers after encoding would be greater than 
$10^{19}/\ln(10^{19}) \approx 2.2\times10^{17},$ an eighteen-digit number.
In short, unless you want to limit yourself to particular classes of
primes (storing only Mersenne primes, for example), you're not
going to be able to reduce the required storage space much by
some clever function that encodes prime numbers using smaller numeric values.
What you can do is to choose a numeric representation that stores
large numbers in fewer bytes of memory.
SQLite 3 provides the INTEGER datatype, which stores an eight-byte signed integer
with a maximum value of about $9\times10^{18}.$
That covers (approximately) the first $2\times10^{17}$ primes.
Will your prime-number search script be searching for primes beyond that?
A: If you are generating them sequentially,
a standard way is to store
the difference between consecutive primes.
This can be done
much more compactly
(I did this many years ago)
by using the fact that
there are only 8 possible primes
between
30n and 30n+29
(they are
30n+1, 7, 11, 13, 17, 19, 23, 29).
By storing 8 bits
in one byte,
each bit telling whether or not
that particular increment
is prime,
the primes in
30n to 30n+29
can be represented by one byte.
Note that
30 = 2x3x5
and
8 = 1x2x4.
To go a little further,
since
210 = 2x3x5x7
and
48 = 1x2x4x6,
the primes from
210n+1 to
210n+211
can be represented in
48 bits.
For the 30 case,
the increments are
2, 6, 4,2, 4, 2, 4, 6.
The algorithm would be
to generate 2, 3, 5, 7 initially.
Then,
with increments of
4,2, 4, 2, 4, 6, 2, 6,
check if the corresponding bit is on
and,
if it is,
output the value as a prime.
To check numbers up to $m$,
you have to compute the
primes up to $\sqrt{m}$
and store them.
