# primecount [![Build Status](https://ci.appveyor.com/api/projects/status/github/kimwalisch/primecount?branch=master&svg=true)](https://ci.appveyor.com/project/kimwalisch/primecount) [![Github Releases](https://img.shields.io/github/release/kimwalisch/primecount.svg)](https://github.com/kimwalisch/primecount/releases) primecount is a command-line program and [C/C++ library](doc/libprimecount.md) that counts the primes below an integer x ≤ 10³¹ using **highly optimized** implementations of the combinatorial [prime counting algorithms](https://en.wikipedia.org/wiki/Prime-counting_function#Algorithms_for_evaluating_%CF%80(x)). primecount includes implementations of all important combinatorial prime counting algorithms known up to this date all of which have been parallelized using [OpenMP](https://en.wikipedia.org/wiki/OpenMP). primecount contains the first ever open source implementations of the Deleglise-Rivat algorithm and Xavier Gourdon's algorithm (that works). primecount also features a [novel load balancer](https://github.com/kimwalisch/primecount/blob/master/src/LoadBalancerS2.cpp) that is shared amongst all implementations and that scales up to hundreds of CPU cores. primecount has already been used to compute several prime counting function [world records](doc/Records.md). ## Installation The primecount command-line program is available in a few package managers. For doing development with libprimecount you may need to install ```libprimecount-dev``` or ```libprimecount-devel```.

Windows:	`winget install primecount`
macOS:	`brew tap kimwalisch/primecount` `brew install primecount`
Arch Linux:	`sudo pacman -S primecount`
Fedora:	`sudo dnf install primecount`
openSUSE:	`sudo zypper install primecount`

## Build instructions You need to have installed a C++ compiler and CMake. Ideally primecount should be compiled using GCC or Clang as these compilers support both OpenMP (multi-threading library) and 128-bit integers. ```sh cmake . make -j sudo make install sudo ldconfig ``` * [Detailed build instructions](doc/BUILD.md) ## Usage examples ```sh # 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 --nth-prime --threads=4 --time ``` ## Command-line options ``` Usage: primecount x [options] Count the number of primes less than or equal to x (<= 10^31). Options: -d, --deleglise-rivat Count primes using the Deleglise-Rivat algorithm -g, --gourdon Count primes using Xavier Gourdon's algorithm. This is the default algorithm. -l, --legendre Count primes using Legendre's formula --lehmer Count primes using Lehmer's formula --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 the nth prime using Li^-1(x) -n, --nth-prime Calculate the nth prime -p, --primesieve Count primes using the sieve of Eratosthenes --phi 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 the nth prime using Ri^-1(x) -s, --status[=NUM] Show computation progress 1%, 2%, 3%, ... Set digits after decimal point: -s1 prints 99.9% --test Run various correctness tests and exit --time Print the time elapsed in seconds -t, --threads=NUM Set the number of threads, 1 <= NUM <= CPU cores. By default primecount uses all available CPU cores. -v, --version Print version and license information -h, --help Print this help menu ```

``` Advanced options for the Deleglise-Rivat algorithm: -a, --alpha=NUM Set tuning factor: y = x^(1/3) * alpha --P2 Compute the 2nd partial sieve function --S1 Compute the ordinary leaves --S2-trivial Compute the trivial special leaves --S2-easy Compute the easy special leaves --S2-hard Compute the hard special leaves Advanced options for Xavier Gourdon's algorithm: --alpha-y=NUM Set tuning factor: y = x^(1/3) * alpha_y --alpha-z=NUM Set tuning factor: z = y * alpha_z --AC Compute the A + C formulas --B Compute the B formula --D Compute the D formula --Phi0 Compute the Phi0 formula --Sigma Compute the 7 Sigma formulas ```

## Benchmarks

x	Prime Count	Legendre	Meissel	Lagarias Miller Odlyzko	Deleglise Rivat	Gourdon
10¹⁰	455,052,511	0.01s	0.01s	0.01s	0.01s	0.00s
10¹¹	4,118,054,813	0.01s	0.01s	0.01s	0.01s	0.01s
10¹²	37,607,912,018	0.03s	0.02s	0.02s	0.01s	0.01s
10¹³	346,065,536,839	0.09s	0.06s	0.03s	0.02s	0.03s
10¹⁴	3,204,941,750,802	0.44s	0.20s	0.08s	0.08s	0.04s
10¹⁵	29,844,570,422,669	2.33s	0.89s	0.29s	0.16s	0.11s
10¹⁶	279,238,341,033,925	15.49s	5.10s	1.26s	0.58s	0.38s
10¹⁷	2,623,557,157,654,233	127.10s	39.39s	5.62s	2.26s	1.34s
10¹⁸	24,739,954,287,740,860	1,071.14s	366.93s	27.19s	9.96s	5.35s
10¹⁹	234,057,667,276,344,607	NaN	NaN	NaN	40.93s	20.16s
10²⁰	2,220,819,602,560,918,840	NaN	NaN	NaN	167.64s	81.98s
10²¹	21,127,269,486,018,731,928	NaN	NaN	NaN	706.70s	353.01s
10²²	201,467,286,689,315,906,290	NaN	NaN	NaN	3,012.10s	1,350.47s

The benchmarks above were run on an AMD 7R32 CPU (from 2020) with 16 cores/32 threads clocked at 3.30GHz. Note that Jan Büthe mentions in [11] that he computed pi(10²⁵) in 40,000 CPU core hours using the analytic prime counting function algorithm. Büthe also mentions that by using additional zeros of the zeta function the runtime could have potentially been reduced to 4,000 CPU core hours. However using primecount and Xavier Gourdon's algorithm pi(10²⁵) can be computed in only 460 CPU core hours on an AMD Ryzen 3950X CPU! ## Performance tips If you have an x64 CPU and you have installed primecount using the package manager of your Linux distribution, then it is possible that the ```POPCNT``` instruction has been disabled in order to ensure that primecount works on very old CPUs. Unfortunately this decreases performance by up to 50%. On the other hand, if you compile primecount from source the ```POPCNT``` instruction will be enabled by default. The fastest primecount binary can be built using the Clang compiler and the ```-march=native``` option. ```bash CXX=clang++ CXXFLAGS="-march=native" cmake . make -j ``` By default primecount scales nicely up until 10²⁰ on current x64 CPUs. For larger values primecount's large memory usage causes many [TLB (translation lookaside buffer)](https://en.wikipedia.org/wiki/Translation_lookaside_buffer) cache misses that significantly deteriorate primecount's performance. Fortunately the Linux kernel allows to enable [transparent huge pages](https://www.kernel.org/doc/html/latest/admin-guide/mm/transhuge.html) so that large memory allocations will automatically be done using huge pages instead of ordinary pages which dramatically reduces the number of TLB cache misses. ```bash # Enable transparent huge pages until next reboot sudo bash -c 'echo always > /sys/kernel/mm/transparent_hugepage/enabled' ``` ## 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] and the implementation of Xavier Gourdon's algorithm is based on Xavier Gourdon's paper [7]. primecount's implementation of the so-called hard special leaves is different from the algorithms that have been described in any of the combinatorial prime counting papers so far. Instead of using a binary indexed tree for counting which is very cache inefficient primecount uses a linear counter array in combination with the POPCNT instruction which is more cache efficient and much faster. The [Hard-Special-Leaves.md](doc/Hard-Special-Leaves.md) document contains more information. primecount's [easy special leaf](doc/Easy-Special-Leaves.md) implementation and its [partial sieve function](doc/Partial-Sieve-Function.md) implementation also contain significant improvements. ## 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: ```--nth-prime```), it finds the nth prime in

operations using

space. ## C API Include the `````` header to use primecount's C API. All functions that are part of primecount's C API return ```-1``` in case an error occurs and print the corresponding error message to the standard error stream. ```C #include #include int main() { int64_t pix = primecount_pi(1000); printf("primes below 1000 = %ld\n", pix); return 0; } ``` * [C API documentation](doc/libprimecount.md#libprimecount) * [libprimecount build instructions](doc/libprimecount.md#build-instructions) ## C++ API Include the `````` header to use primecount's C++ API. All functions that are part of primecount's C++ API throw a ```primecount_error``` exception (which is derived from ```std::exception```) in case an error occurs. ```C++ #include #include int main() { int64_t pix = primecount::pi(1000); std::cout << "primes below 1000 = " << pix << std::endl; return 0; } ``` * [C++ API documentation](doc/libprimecount.md#libprimecount) * [libprimecount build instructions](doc/libprimecount.md#build-instructions) ## Bindings for other languages primesieve natively supports C and C++ and has bindings available for:

Common Lisp:	cl-primecount
Julia:	primecount_jll.jl
Haskell:	hprimecount
Python:	primecountpy
Python:	primecount-python
Rust:	primecount-rs

Many thanks to the developers of these bindings!