Skip to content

libprimecount.md

Latest commit

 

History

History
233 lines (180 loc) · 8.57 KB

libprimecount.md

File metadata and controls

233 lines (180 loc) · 8.57 KB
Raw

libprimecount

primecount can be built as a static and shared C/C++ library for use in other math projects. libprimecount has both a C API (<primecount.h> header) and a C++ API (<primecount.hpp> header) so you are free to pick the one that best fits your needs. The C API has been added to make it easier to write libprimecount bindings for other programming languages.

primecount's prime counting function implementation and nth prime function are generally orders of magnitude faster than other publicly available prime counting function implementations. As of 2021 libprimecount is the only prime counting function library that I am aware of that supports multi-threading. libprimecount is also very portable, it has been tested successfully on a wide range of operating systems, compilers (GCC, Clang, MSVC) and CPU architectures (x86, x64, ARM, ARM64, PowerPC, PP64, Sparc).

libprimecount has been integrated into a few other computer algebra systems: Since 2021 Mathematica's PrimePi(x) uses libprimecount under the hood, primecount is available as an optional package in SageMath and there are bindings available for a few other programming languages. If your company uses primecount then I would greatly appreciate if you would sponsor its maintenance (or donate). The development of primecount has personally cost me a lot of money, as I frequently needed to run extensive benchmarks on a wide variety of high end cloud servers.

Contents

C API reference

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.

// Count the number of primes <= x
int64_t primecount_pi(int64_t x);

// Count the number of primes <= x (supports 128-bit)
pc_int128_t primecount_pi_128(pc_int128_t x);

// Find the nth prime e.g.: nth_prime(25) = 97
int64_t primecount_nth_prime(int64_t n);

// Find the nth prime (supports 128-bit)
pc_int128_t primecount_nth_prime_128(pc_int128_t n);

// Count the numbers <= x that are not divisible by any of the first a primes
int64_t primecount_phi(int64_t x, int64_t a);

Please check <primecount.h> for detailed function specifications.

C example

The C example below counts the primes ≤ 1000 and prints the result to the screen. Note that primecount is multi-threaded by default, it uses all available CPU cores if the input is sufficiently large.

#include <primecount.h>
#include <stdio.h>

int main()
{
    int64_t pix = primecount_pi(1000);
    printf("primes below 1000 = %ld\n", pix);

    return 0;
}

Compile using:

cc -O3 primes.c -o primes -lprimecount

If you have built libprimecount yourself, then the default installation path is usually /usr/local/lib. Running the ldconfig program after make install ensures that Linux's dynamic linker/loader will find the shared primecount library when you execute your program. However, some OSes are missing the ldconfig program or ldconfig does not include /usr/local/lib by default. In these cases you need to export some environment variables:

export LIBRARY_PATH=/usr/local/lib:$LIBRARY_PATH
export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH
export C_INCLUDE_PATH=/usr/local/include:$C_INCLUDE_PATH

C++ API reference

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.

// Count the number of primes <= x
int64_t primecount::pi(int64_t x);

// Count the number of primes <= x (supports 128-bit)
pc_int128_t primecount::pi(pc_int128_t x);

// Find the nth prime e.g.: nth_prime(25) = 97
int64_t primecount::nth_prime(int64_t n);

// Find the nth prime (supports 128-bit)
pc_int128_t primecount::nth_prime(pc_int128_t n);

// Count the numbers <= x that are not divisible by any of the first a primes
int64_t primecount::phi(int64_t x, int64_t a);

Please check <primecount.hpp> for detailed function specifications.

C++ example

The C++ example below counts the primes ≤ 1000 and prints the result to the screen. Note that primecount is multi-threaded by default, it uses all available CPU cores if the input is sufficiently large.

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

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

    return 0;
}

Compile using:

c++ -O3 primes.cpp -o primes -lprimecount

If you have built libprimecount yourself, then the default installation path is usually /usr/local/lib. Running the ldconfig program after make install ensures that Linux's dynamic linker/loader will find the shared primecount library when you execute your program. However, some OSes are missing the ldconfig program or ldconfig does not include /usr/local/lib by default. In these cases you need to export some environment variables:

export LIBRARY_PATH=/usr/local/lib:$LIBRARY_PATH
export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH
export CPLUS_INCLUDE_PATH=/usr/local/include:$CPLUS_INCLUDE_PATH

pkgconf support

primecount also has support for the pkgconf program which allows to easily compile C and C++ programs depending on libprimecount without having to care about the library and include paths:

cc -O3 main.c -o main $(pkgconf --libs --cflags primecount)

CMake: find_package(primecount)

If you are using the CMake build system to compile your program and libprimecount is installed on your system, then you can use the following minimal CMakeLists.txt to link your program against libprimecount:

# CMakeLists.txt
project(my_project C CXX)
find_package(primecount REQUIRED)
add_executable(my_exec main.c)
target_link_libraries(my_exec primecount::primecount)

Build instructions

You need to have installed a C++ compiler, cmake and make. By default, only the static libprimecount is built, but for doing development with libprimecount you will most likely want to use the shared libprimecount. Hence we use the -DBUILD_SHARED_LIBS=ON option to enable building libprimecount as a shared library.

cmake . -DBUILD_SHARED_LIBS=ON
cmake --build . --parallel
sudo cmake --install .
sudo ldconfig

CMake build options

Here are all available cmake configuration options:

option(BUILD_PRIMECOUNT     "Build the primecount binary"           ON)
option(BUILD_LIBPRIMESIEVE  "Build libprimesieve"                   ON)
option(BUILD_SHARED_LIBS    "Build the shared libprimecount"        OFF)
option(BUILD_STATIC_LIBS    "Build the static libprimecount"        ON)
option(BUILD_MANPAGE        "Regenerate man page using a2x program" OFF)
option(BUILD_TESTS          "Build the test programs"               OFF)

option(WITH_LIBDIVIDE       "Use libdivide.h"                       ON)
option(WITH_OPENMP          "Enable OpenMP multi-threading"         ON)
option(WITH_MULTIARCH       "Enable runtime dispatching to fastest supported CPU instruction set" ON)
option(WITH_DIV32           "Use 32-bit division instead of 64-bit division whenever possible" OFF)
option(WITH_FLOAT128        "Use __float128 (requires libquadmath), increases precision of Li(x) & RiemannR" OFF)