primecount is a command-line program and C/C++ library that counts the number of primes ≤ x (maximum 1031) using highly optimized implementations of the combinatorial prime counting algorithms.
primecount includes implementations of all important combinatorial prime counting algorithms known up to this date all of which have been parallelized using 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 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.
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 install primecount |
| Arch Linux: | sudo pacman -S primecount |
| Debian/Ubuntu: | sudo apt install primecount |
| Fedora: | sudo dnf install primecount |
| FreeBSD: | pkg install primecount |
| openSUSE: | sudo zypper install primecount |
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.
cmake .
cmake --build . --parallel
sudo cmake --install .
sudo ldconfig# Count the primes ≤ 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 --timeUsage: 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 Eulerian logarithmic integral function
--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 <X> <A> phi(x, a) counts the numbers <= x that are not
divisible by any of the first a primes
-R, --RiemannR Approximate pi(x) using the Riemann R function
--RiemannR-inverse Approximate the nth prime using R^-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
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
| x | Prime Count | Legendre | Meissel | Lagarias Miller Odlyzko |
Deleglise Rivat |
Gourdon |
| 1010 | 455,052,511 | 0.01s | 0.01s | 0.01s | 0.01s | 0.00s |
| 1011 | 4,118,054,813 | 0.01s | 0.01s | 0.01s | 0.01s | 0.01s |
| 1012 | 37,607,912,018 | 0.03s | 0.02s | 0.02s | 0.01s | 0.01s |
| 1013 | 346,065,536,839 | 0.09s | 0.06s | 0.03s | 0.02s | 0.03s |
| 1014 | 3,204,941,750,802 | 0.44s | 0.20s | 0.08s | 0.08s | 0.04s |
| 1015 | 29,844,570,422,669 | 2.33s | 0.89s | 0.29s | 0.16s | 0.11s |
| 1016 | 279,238,341,033,925 | 15.49s | 5.10s | 1.26s | 0.58s | 0.38s |
| 1017 | 2,623,557,157,654,233 | 127.10s | 39.39s | 5.62s | 2.26s | 1.34s |
| 1018 | 24,739,954,287,740,860 | 1,071.14s | 366.93s | 27.19s | 9.96s | 5.35s |
| 1019 | 234,057,667,276,344,607 | NaN | NaN | NaN | 40.93s | 20.16s |
| 1020 | 2,220,819,602,560,918,840 | NaN | NaN | NaN | 167.64s | 81.98s |
| 1021 | 21,127,269,486,018,731,928 | NaN | NaN | NaN | 706.70s | 353.01s |
| 1022 | 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
| 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
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 document contains more information. primecount's easy special leaf implementation and its partial sieve function implementation also contain significant improvements.
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
primecount::nth_prime(n) this way
(option: --nth-prime), it finds the nth prime in
Include the <primecount.h> 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.
#include <primecount.h>
#include <stdio.h>
int main()
{
int64_t pix = primecount_pi(1000);
printf("primes <= 1000: %ld\n", pix);
return 0;
}Include the <primecount.hpp> 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.
#include <primecount.hpp>
#include <iostream>
int main()
{
int64_t pix = primecount::pi(1000);
std::cout << "primes <= 1000: " << pix << std::endl;
return 0;
}primesieve natively supports C and C++ and has bindings available for:
| Common Lisp: | cl-primecount |
| Julia: | primecount_jll.jl |
| Lua: | lua-primecount |
| Haskell: | primecount-haskell |
| Python: | primecountpy |
| Python: | primecount-python |
| Rust: | primecount-rs |
Many thanks to the developers of these bindings!