🚀 Fast C++ prime counting function implementation
Clone or download
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
doc Fix missing spaces Mar 27, 2018
include Silence clang-cl -Wdeprecated warning Aug 15, 2018
lib/primesieve Update to libprimesieve 7.2 Oct 26, 2018
scripts Update worktodo.sh Jun 21, 2017
src Simplify print API May 9, 2018
test Get rid of prt::make_signed May 7, 2018
.gitignore Ignore build directory May 5, 2018
.travis.yml Use -Wno-long-long Feb 18, 2018
CMakeLists.txt Improve OpenMP detection May 6, 2018
COPYING Update copyright year Jan 27, 2018
ChangeLog Changes in version 4.4 May 9, 2018
README.md Update version to 4.4 May 9, 2018
appveyor.yml Revert Jan 21, 2018

README.md

primecount

Build Status Build Status Github Releases

primecount is a command-line program and C++ library that counts the primes below an integer x ≤ 1031 using highly optimized implementations of the prime counting function (combinatorial methods). primecount includes implementations of the algorithms of Legendre, Meissel, Lehmer, Lagarias-Miller-Odlyzko and Deleglise-Rivat all of which have been parallelized using OpenMP. The Deleglise-Rivat implementation has also been distributed using MPI.

primecount contains the first ever parallel open source implementation of the Deleglise-Rivat algorithm and it features a novel load balancer which scales up to hundreds of CPU cores. primecount has already been used to compute several world records e.g. pi(1027) and nth_prime(1024), more will hopefully follow!

Build instructions

You need to have installed a C++ compiler, cmake and make. Ideally primecount should be compiled using a C++ compiler that supports both OpenMP and 128-bit integers (e.g. GCC, Clang, Intel C++ Compiler).

cmake .
make -j
sudo make install

To build primecount using MPI support for distributing computations onto cluster nodes use:

cmake -DWITH_MPI=ON .

primecount-MPI.md contains more information.

Binaries

Below are the latest precompiled primecount binaries for Windows, Linux and macOS. These binaries are statically linked and require a CPU which supports the POPCNT instruction (2010 or later).

Usage examples

Open a terminal and run primecount using e.g.:

# Count the primes below 10^14
./primecount 1e14

# Print progress and status information during computation
./primecount 1e20 --status

# Count primes using Meissel's algorithm
./primecount 2**32 --meissel

# Find the 10^14th prime using 4 threads
./primecount 1e14 --nthprime --threads=4 --time

Command-line options

Usage: primecount x [OPTION]...
Count the primes below x <= 10^31 using fast implementations of the
combinatorial prime counting function.

Options:

  -d,    --deleglise_rivat  Count primes using Deleglise-Rivat algorithm
         --legendre         Count primes using Legendre's formula
         --lehmer           Count primes using Lehmer's formula
  -l,    --lmo              Count primes using Lagarias-Miller-Odlyzko
  -m,    --meissel          Count primes using Meissel's formula
         --Li               Approximate pi(x) using the logarithmic integral
         --Li_inverse       Approximate nth prime using Li^-1(x)
  -n,    --nthprime         Calculate the nth prime
  -p,    --primesieve       Count primes using the sieve of Eratosthenes
         --phi=<a>          phi(x, a) counts the numbers <= x that are
                            not divisible by any of the first a primes
         --Ri               Approximate pi(x) using Riemann R
         --Ri_inverse       Approximate nth prime using Ri^-1(x)
  -s[N], --status[=N]       Show computation progress 1%, 2%, 3%, ...
                            [N] digits after decimal point e.g. N=1, 99.9%
         --test             Run various correctness tests and exit
         --time             Print the time elapsed in seconds
  -t<N>, --threads=<N>      Set the number of threads, 1 <= N <= CPU cores
  -v,    --version          Print version and license information
  -h,    --help             Print this help menu

Advanced Deleglise-Rivat options:

  -a<N>, --alpha=<N>        Tuning factor, 1 <= alpha <= x^(1/6)
         --P2               Only compute the 2nd partial sieve function
         --S1               Only compute the ordinary leaves
         --S2_trivial       Only compute the trivial special leaves
         --S2_easy          Only compute the easy special leaves
         --S2_hard          Only compute the hard special leaves

C++ library

primecount can be built as a static and shared C++ library for use in other math projects.

#include <primecount.hpp>
#include <iostream>

int main()
{
    int64_t primes = primecount::pi(1000);
    std::cout << "primes below 1000 = " << primes << std::endl;

    return 0;
}

libprimecount.md contains more information.

Algorithms

Legendre's Formula
Meissel's Formula
Lehmer's Formula
LMO Formula

Up until the early 19th century the most efficient known method for counting primes was the sieve of Eratosthenes which has a running time of operations. The first improvement to this bound was Legendre's formula (1830) which uses the inclusion-exclusion principle to calculate the number of primes below x without enumerating the individual primes. Legendre's formula has a running time of operations and uses space. In 1870 E. D. F. Meissel improved Legendre's formula by setting and by adding the correction term . Meissel's formula has a running time of operations and uses space. In 1959 D. H. Lehmer extended Meissel's formula and slightly improved the running time to operations and space. In 1985 J. C. Lagarias, V. S. Miller and A. M. Odlyzko published a new algorithm based on Meissel's formula which has a lower runtime complexity of operations and which uses only space.

primecount's Legendre, Meissel and Lehmer implementations are based on Hans Riesel's book [5], its Lagarias-Miller-Odlyzko and Deleglise-Rivat implementations are based on Tomás Oliveira's paper [9].

Fast nth prime calculation

The most efficient known method for calculating the nth prime is a combination of the prime counting function and a prime sieve. The idea is to closely approximate the nth prime (e.g. using the inverse logarithmic integral or the inverse Riemann R function ) and then count the primes up to this guess using the prime counting function. Once this is done one starts sieving (e.g. using the segmented sieve of Eratosthenes) from there on until one finds the actual nth prime. The author has implemented primecount::nth_prime(n) this way (option: --nthprime), it finds the nth prime in operations using space.

Benchmark

x Prime Count Legendre Meissel Lagarias
Miller
Odlyzko
Deleglise
Rivat
1010 455,052,511 0.02s 0.01s 0.01s 0.01s
1011 4,118,054,813 0.03s 0.02s 0.01s 0.01s
1012 37,607,912,018 0.10s 0.06s 0.03s 0.02s
1013 346,065,536,839 0.46s 0.26s 0.06s 0.04s
1014 3,204,941,750,802 2.66s 1.28s 0.19s 0.10s
1015 29,844,570,422,669 17.51s 7.65s 0.73s 0.35s
1016 279,238,341,033,925 136.16s 55.30s 2.95s 1.26s
1017 2,623,557,157,654,233 1,155.34s 456.08s 12.49s 4.57s
1018 24,739,954,287,740,860 10,239.22s 3,974.21s 55.87s 18.97s
1019 234,057,667,276,344,607 NaN NaN NaN 86.13s
1020 2,220,819,602,560,918,840 NaN NaN NaN 373.09s
1021 21,127,269,486,018,731,928 NaN NaN NaN 1,747.57s
1022 201,467,286,689,315,906,290 NaN NaN NaN 8,215.59s

The benchmarks above were run on an AMD Ryzen 7 1700 CPU (8 x 3.0 GHz, 3.7 GHz Turbo) from 2017 and primecount was compiled using GCC 6.3.