A tool for working with prime numbers.
When calculating prime numbers, highly efficient algorithms are usually employed, often based on sieves (such as the sieve of Eratosthenes). Yet even these algorithms struggle with very large primes, as memory usage grows rapidly when building a sieve. A partial remedy is the use of segmented sieve algorithms, though they too lose efficiency when constructing extremely large sieves.
This project serves as a demonstration that prime numbers need not always be computed at runtime – they can instead be precomputed and embedded directly into the program.
The idea is that primes can be stored efficiently in binary form, allocating just 4 bytes per number. But rather than creating a database of prime numbers, the approach is to store the half-values of prime gaps (skipping only the first prime pair: 2 and 3). In this scheme, each prime number can be reconstructed by doubling the stored half-gap and adding it to the previous prime number. By doing so, the size of the binary database can be reduced from ~775.45 MB to ~195 MB, which can be further compressed to ~110 MB.
This method leverages the fact that the differences between consecutive primes grow slowly relative to the primes themselves, allowing the storage of smaller values in a compact form. Consequently, the database becomes significantly more space-efficient without sacrificing the ability to reconstruct the full sequence of primes at runtime.
To run, the program requires RAM equal to the size of the prime database (~775.45 MB) plus a small overhead – totaling up to ~778 MB. Decompression needs an additional 32 MB (because LZMA2:25 requires 2²⁵ bytes for decompression) plus the size of the database of halves of prime gaps (~195 MB), resulting in a peak memory requirement of about ~1004 MB during startup. Once running, it uses ~778 MB.