# primesieve [![Build Status](https://ci.appveyor.com/api/projects/status/github/kimwalisch/primesieve?branch=master&svg=true)](https://ci.appveyor.com/project/kimwalisch/primesieve) [![Github Releases](https://img.shields.io/github/release/kimwalisch/primesieve.svg)](https://github.com/kimwalisch/primesieve/releases) primesieve is a command-line program and C/C++ library for quickly generating prime numbers. It is very cache efficient, it detects your CPU's L1 & L2 cache sizes and allocates its main data structures accordingly. It is also multi-threaded by default, it uses all available CPU cores whenever possible i.e. if sequential ordering is not required. primesieve can generate primes and [prime k-tuplets](https://en.wikipedia.org/wiki/Prime_k-tuple) up to 2⁶⁴. primesieve generates primes using the segmented [sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) with [wheel factorization](https://en.wikipedia.org/wiki/Wheel_factorization). This algorithm has a run time complexity of

operations and uses

memory. Furthermore primesieve uses the [bucket sieve](http://sweet.ua.pt/tos/software/prime_sieve.html) algorithm which improves the cache efficiency when generating primes > 2³². primesieve uses 8 bytes per sieving prime, hence its memory usage is about

bytes per thread. * [More algorithm details](doc/ALGORITHMS.md) ## Installation The primesieve command-line program can be installed using your operating system's package manager. For doing development with libprimesieve you may need to install ```libprimesieve-dev``` or ```libprimesieve-devel```.

Windows:	`winget install primesieve`
macOS:	`brew install primesieve`
Arch Linux:	`sudo pacman -S primesieve`
Chocolatey:	`choco install primesieve`
Debian/Ubuntu:	`sudo apt install primesieve`
Fedora:	`sudo dnf install primesieve`
FreeBSD:	`pkg install primesieve`
openSUSE:	`sudo zypper install primesieve`

## Usage examples ```sh # Count the primes below 1e10 using all CPU cores primesieve 1e10 # Print the primes below 1000000 primesieve 1000000 --print # Print the twin primes below 1000000 primesieve 1000000 --print=2 # Count the prime triplets inside [1e10, 1e10+2^32] primesieve 1e10 --dist=2^32 --count=3 ``` ## Command-line options ``` Usage: primesieve [START] STOP [OPTION]... Generate the primes and/or prime k-tuplets inside [START, STOP] (< 2^64) using the segmented sieve of Eratosthenes. Options: -c, --count[=NUM+] Count primes and/or prime k-tuplets, NUM <= 6. Count primes: -c or --count (default option), count twin primes: -c2 or --count=2, count prime triplets: -c3 or --count=3, ... --cpu-info Print CPU information (cache sizes). -d, --dist=DIST Sieve the interval [START, START + DIST]. -h, --help Print this help menu. -n, --nth-prime Find the nth prime. primesieve 100 -n: finds the 100th prime, primesieve 2 100 -n: finds the 2nd prime > 100. --no-status Turn off the progressing status. -p, --print[=NUM] Print primes or prime k-tuplets, NUM <= 6. Print primes: -p or --print, print twin primes: -p2 or --print=2, print prime triplets: -p3 or --print=3, ... -q, --quiet Quiet mode, prints less output. -s, --size=SIZE Set the sieve size in KiB, SIZE <= 4096. By default primesieve uses a sieve size that matches your CPU's L1 cache size (per core) or is slightly smaller than your CPU's L2 cache size. --test Run various sieving tests. -t, --threads=NUM Set the number of threads, NUM <= CPU cores. Default setting: use all available CPU cores. --time Print the time elapsed in seconds. -v, --version Print version and license information. ``` ## Build instructions You need to have installed a C++ compiler which supports C++11 (or later) and CMake ≥ 3.4. ```sh cmake . make -j sudo make install sudo ldconfig ``` * [Detailed build instructions](doc/BUILD.md) ## C++ API Include the `````` header to use libprimesieve's C++ API. ```C++ #include #include int main() { primesieve::iterator it; uint64_t prime = it.next_prime(); // Iterate over the primes below 10^6 for (; prime < 1000000; prime = it.next_prime()) std::cout << prime << std::endl; return 0; } ``` * [More C++ examples](doc/CPP_Examples.md) * [C++ API reference](https://kimwalisch.github.io/primesieve/api) ## C API Include the `````` header to use libprimesieve's C API. ```C #include #include #include int main() { primesieve_iterator it; primesieve_init(&it); uint64_t prime; /* Iterate over the primes below 10^6 */ while ((prime = primesieve_next_prime(&it)) < 1000000) printf("%" PRIu64 "\n", prime); primesieve_free_iterator(&it); return 0; } ``` * [More C examples](doc/C_Examples.md) * [C API reference](https://kimwalisch.github.io/primesieve/api) ## libprimesieve performance tips * ```primesieve::iterator::next_prime()``` runs up to 2x faster and uses only half as much memory as ```prev_prime()```. Oftentimes algorithms that iterate over primes using ```prev_prime()``` can be rewritten using ```next_prime()``` which improves performance in most cases. * ```primesieve::iterator``` is single-threaded. See the [multi-threading](#libprimesieve-multi-threading) section for how to parallelize an algorithm using multiple ```primesieve::iterator``` objects. * The ```primesieve::iterator``` constructor and the ```primesieve::iterator::skipto()``` method take an optional ```stop_hint``` parameter that can provide a significant speedup if the sieving distance is relatively small e.g. < sqrt(start). If ```stop_hint``` is set ```primesieve::iterator``` will only buffer primes up to this limit. * Many of libprimesieve's functions e.g. ```count_primes(start, stop)``` & ```nth_prime(n, start)``` incur an initialization overhead of O(sqrt(start)) even if the total sieving distance is tiny. It is therefore not a good idea to call these functions repeatedly in a loop unless the sieving distance is sufficiently large e.g. > sqrt(start). If the sieving distance is mostly small consider using a ```primesieve::iterator``` instead to avoid the recurring initialization overhead. ## libprimesieve multi-threading By default libprimesieve uses multi-threading for counting primes/k-tuplets and for finding the nth prime. However ```primesieve::iterator``` the most useful feature provided by libprimesieve runs single-threaded because it is simply not possible to efficiently parallelize the generation of primes in sequential order. Hence if you want to parallelize an algorithm using ```primesieve::iterator``` you need to implement the multi-threading part yourself. The basic technique for parallelizing an algorithm using ```primesieve::iterator``` is: * Subdivide the sieving distance into equally sized chunks. * Process each chunk in its own thread. * Combine the partial thread results to get the final result. The C++ example below calculates the sum of the primes ≤ 10¹⁰ in parallel using [OpenMP](https://en.wikipedia.org/wiki/OpenMP). Each thread processes a chunk of size ```(dist / threads) + 1``` using its own ```primesieve::iterator``` object. The OpenMP reduction clause takes care of adding the partial prime sum results together in a thread safe manner. ```C++ #include #include #include int main() { uint64_t sum = 0; uint64_t dist = 1e10; int threads = omp_get_max_threads(); uint64_t thread_dist = (dist / threads) + 1; #pragma omp parallel for reduction(+: sum) for (int i = 0; i < threads; i++) { uint64_t start = i * thread_dist; uint64_t stop = std::min(start + thread_dist, dist); primesieve::iterator it(start, stop); uint64_t prime = it.next_prime(); for (; prime <= stop; prime = it.next_prime()) sum += prime; } std::cout << "Sum of the primes below " << dist << ": " << sum << std::endl; return 0; } ```

Build instructions

```bash # Unix-like OSes wget https://kimwalisch.github.io/primesieve/primesum.cpp c++ -O3 -fopenmp primesum.cpp -o primesum -lprimesieve time ./primesum ```

## Linking against libprimesieve #### Unix-like OSes ```sh c++ -O3 primes.cpp -lprimesieve cc -O3 primes.c -lprimesieve ``` If you have [built libprimesieve yourself](BUILD.md#primesieve-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 primesieve 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 export C_INCLUDE_PATH=/usr/local/include:$C_INCLUDE_PATH ``` #### Microsoft Visual C++ ```sh cl /O2 /EHsc /MD primes.cpp /I "path\to\primesieve\include" /link "path\to\primesieve.lib" ``` ## CMake support If you are using the CMake build system to compile your program and [libprimesieve is installed](https://github.com/kimwalisch/primesieve#installation) on your system, then you can add the following two lines to your ```CMakeLists.txt``` to link your program against libprimesieve. ```CMake find_package(primesieve REQUIRED) target_link_libraries(your_program primesieve::primesieve) ``` To link against the static libprimesieve use: ```CMake find_package(primesieve REQUIRED static) target_link_libraries(your_program primesieve::primesieve) ``` * Example [CMakeLists.txt](doc/C_Examples.md#minimal-cmake-project-file) for C programs * Example [CMakeLists.txt](doc/CPP_Examples.md#minimal-cmake-project-file) for C++ programs ## Bindings for other languages primesieve natively supports C and C++ and has bindings available for:

Common Lisp:	cl-primesieve
Julia:	PrimeSieve.jl
Nim:	primesievec-nim
Haskell:	primesieve-haskell
Pascal:	primesieve-pas
Perl:	Primesieve
Python:	primesieve-python
Raku:	raku-primesieve
Ruby:	primesieve-ruby
Rust:	primesieve.rs

Many thanks to the developers of these bindings!