# 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)](https://reference.wolfram.com/language/ref/PrimePi.html)
uses libprimecount under the hood, primecount is available as an
optional package in
[SageMath](https://doc.sagemath.org/html/en/reference/spkg/primecount.html) and
there are bindings available for a few
[other programming languages](https://github.com/kimwalisch/primecount#bindings-for-other-languages).
If your company uses primecount then I would greatly appreciate if you would
[sponsor](https://github.com/sponsors/kimwalisch) its maintenance (or
[donate](https://github.com/sponsors/kimwalisch?frequency=one-time&sponsor=kimwalisch)).
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](#c-api-reference)
* [C example](#c-example)
* [C++ API reference](#c-api-reference-1)
* [C++ example](#c-example-1)
* [pkgconf support](#pkgconf-support)
* [Install libprimecount using package manager](https://github.com/kimwalisch/primecount#installation)
* [Build libprimecount from source](#build-instructions)
* [Maximum portability](#maximum-portability)
* [CMake build options](#cmake-build-options)

# 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.

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

// Count the number of primes <= x (supports 128-bit)
int primecount_pi_str(const char* x, char* res, size_t len);

// Find the nth prime e.g.: nth_prime(25) = 97
int64_t primecount_nth_prime(int64_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 see [primecount.h](https://github.com/kimwalisch/primecount/blob/master/include/primecount.h)
for more information.

# 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.

```C
#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:

```sh
cc -O3 primes.c -o primes -lprimecount
```

If you have [built libprimecount yourself](#Build-instructions),
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:

```sh
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.

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

// Count the number of primes <= x (supports 128-bit)
std::string primecount::pi(const std::string& x);

// Find the nth prime e.g.: nth_prime(25) = 97
int64_t primecount::nth_prime(int64_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 see [primecount.hpp](https://github.com/kimwalisch/primecount/blob/master/include/primecount.hpp)
for more information.

# 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.

```C++
#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:

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

If you have [built libprimecount yourself](#Build-instructions),
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:

```sh
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](https://github.com/pkgconf/pkgconf) program which
allows to easily compile C and C++ programs depending on libprimecount
without having to care about the library and include paths:

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

# Build instructions

You need to have [installed a C++ compiler, cmake and make](BUILD.md#prerequisites). 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.

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

* [Detailed build instructions](BUILD.md#primecount-build-instructions)

# Maximum portability

For performance reasons primecount uses the ```POPCNT``` instruction on all
CPU architectures that support it. Enabling the ```POPCNT``` instruction
usually improves primecount's performance by about 30%.

On x86/x64 CPUs primecount will by default detect at build time if the host
CPU supports the ```POPCNT``` instruction. If not, the ```POPCNT```
instruction will be disabled and a portable alternative algorithm will be used.
If you need to build a portable primecount binary package for x86/x64 CPUs that
can be distributed to many different PCs, even very old ones without
```POPCNT``` support (2008 or earlier), you need to disable the ```POPCNT```
instruction at build time. Note that disabling ```POPCNT``` only has an effect
on x86/x64, on other CPU architectures ```POPCNT``` is always used if it is
available (as this generally does not cause any issues).

```
cmake . -DWITH_POPCNT=OFF
```

# CMake build options

Here are all available cmake configuration options:

```CMake
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_POPCNT          "Use the POPCNT instruction"            ON)
option(WITH_LIBDIVIDE       "Use libdivide.h"                       ON)
option(WITH_OPENMP          "Enable OpenMP multi-threading"         ON)
option(WITH_DIV32           "Use 32-bit division instead of 64-bit division whenever possible" ON)
option(WITH_MSVC_CRT_STATIC "Link primecount.lib with /MT instead of the default /MD" OFF)
option(WITH_FLOAT128        "Use __float128 (requires libquadmath), increases precision of Li(x) & RiemannR" OFF)
option(WITH_JEMALLOC        "Use jemalloc allocator"                OFF)
```