primesieve

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 up to 2⁶⁴.

primesieve generates primes using the segmented sieve of Eratosthenes with wheel factorization. This algorithm has a run time complexity of operations and uses memory. Furthermore primesieve uses the bucket sieve 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

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

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

cmake .
make -j
sudo make install
sudo ldconfig

• Detailed build instructions

C++ API

Include the <primesieve.hpp> header to use libprimesieve's C++ API.

#include <primesieve.hpp>
#include <iostream>

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
• C++ API reference

C API

Include the <primesieve.h> header to use libprimesieve's C API.

#include <primesieve.h>
#include <inttypes.h>
#include <stdio.h>

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
• C API reference

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

#include <primesieve.hpp>
#include <iostream>
#include <omp.h>

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

# 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

c++ -O3 primes.cpp -lprimesieve
cc  -O3 primes.c   -lprimesieve

If you have built libprimesieve 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 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:

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++

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 on your system, then you can add the following two lines to your CMakeLists.txt to link your program against libprimesieve.

find_package(primesieve REQUIRED)
target_link_libraries(your_program primesieve::primesieve)

To link against the static libprimesieve use:

find_package(primesieve REQUIRED static)
target_link_libraries(your_program primesieve::primesieve)

• Example CMakeLists.txt for C programs
• Example CMakeLists.txt 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!