High Performance Storage of Prime Numbers

Although modern computers and algorithms can generate very large prime sets in a relatively short time, storing and distributing the resulting data remains a significant practical problem.This paper investigates a storage format that exploits the specific properties of prime numbers. Instead of representing every integer up to a limit, the proposed format allocates one bit only to integers that are coprime to a small primorial. The resulting bitmap can subsequently be further compressed using a general purpose compressor such as gzip.Experiments on a representative interval near 10^13 show that the compressed representation using 23# (primorial of 23) requires approximately 0.46 bytes per prime. At this rate, storing the first 10^12 prime numbers would require less than 450 GiB of storage.