Fast prime counting function library
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 primecountYou 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 ( phi(x, a) counts the numbers
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…primecount::nth_prime(n)this way (option:--nth-prime```), it finds the nth prime in $O(x^{\frac{2}{3}}/\log^2{x})$
operations using $O(\sqrt[3]{x}\ \log^3{x})$ space.
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.
#include
#include
int main()
{
int64_t pix = primecount_pi(1000);
printf("primes <= 1000: %ld\n", pix);
return 0;
}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.
#include
#include
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
Rust:
primecount-rsMany thanks to the developers of these bindings!
Thanks to all current and past sponsors of primecount! Your donations help me purchase (or rent) the latest CPUs and ensure primecount runs at maximum performance on them. Your donations also motivate me to continue maintaining primecount.
No open issues yet, or sync has not completed.