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 O(n\ \log\ \log\ n) operations and uses O(\sqrt{n}) memory. Furthermore primesieve uses the bucket sieve algorithm which improves the cache efficiency when generating primes > 2³². primesieve uses 8 bytes per sieving prime, in practice its memory usage is about \pi(\sqrt{n})\times 8 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
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 ≤ 1e10 using all CPU cores
primesieve 1e10

# Print the primes ≤ 1000000
primesieve 1000000 --print

# Store the primes ≤ 1000000 in a text file
primesieve 1000000 --print > primes.txt

# Print the twin primes ≤ 1000000
primesieve 1000000 --print=2

# Count the prime triplets inside [1e10, 1e10+2^32]
primesieve 1e10 --dist=2^32 --count=3

# Count the primes ≤ 1e11 on a GPU
primesieve 1e11 --count --gpu

Note that printing primes and storing them in a text file are not primesieve's primary use cases: both run single-threaded as printing requires sequential ordering, and both use the same standard output path rather than file-specific I/O optimizations. For maximum throughput, generate primes in memory using libprimesieve.

GPU support

primesieve can count primes and prime k-tuplets on a GPU, using either OpenCL or CUDA. The GPU runs the same segmented sieve of Eratosthenes as the CPU, with the same wheel-30 bit array, so the counts are identical.

primesieve --gpu-info        # list the GPU devices
primesieve 1e11 --gpu        # ~2x faster than 12 CPU threads on a laptop RTX 3050

Both backends are built by default and neither needs an SDK: the OpenCL ICD loader, and the CUDA driver plus NVRTC, are all resolved at runtime, so libprimesieve still builds and runs on machines with no GPU runtime installed. --gpu never changes the answer — small ranges, printing, and machines without a working GPU fall back to the CPU sieve automatically.

See doc/GPU.md for the API, the tuning knobs, how the kernel works and the measured results.

Stress testing

primesieve includes support for stress testing both the CPU and memory. This feature is useful for checking system stability under maximum load and verifying whether your cooling solution (fans, heatsinks, thermal paste, etc.) is adequate. primesieve's stress test supports two modes: CPU (highest CPU load, uses little memory) and RAM (high memory usage, uses about 1.2 GiB per thread).

$ primesieve --stress-test --timeout 5m
Started CPU stress testing using 14 threads.
The expected memory usage is: 14 threads * 2.85 MiB = 39.90 MiB.
The stress test keeps on running until either a miscalculation occurs
(due to a hardware issue) or the timeout of 5m expires.
You may cancel the stress test at any time using Ctrl+C.

[Apr 12 19:09] Thread 14, 25.19 secs, PrimePi(1e13+98e11, 1e13+99e11) = 3265923128   OK
[Apr 12 19:09] Thread  9, 32.48 secs, PrimePi(1e13+63e11, 1e13+64e11) = 3286757785   OK
[Apr 12 19:09] Thread 14, 22.32 secs, PrimePi(1e13+ 0e11, 1e13+ 1e11) = 3340141707   OK
[Apr 12 19:10] Thread  2, 17.10 secs, PrimePi(1e13+16e11, 1e13+17e11) = 3323791292   OK
[Apr 12 19:10] Thread 14, 18.45 secs, PrimePi(1e13+ 3e11, 1e13+ 4e11) = 3336895789   OK
[Apr 12 19:11] Thread 13, 16.96 secs, PrimePi(1e13+96e11, 1e13+97e11) = 3267004191   OK
[Apr 12 19:11] Thread  2, 31.79 secs, PrimePi(1e13+20e11, 1e13+21e11) = 3320071119   OK
[Apr 12 19:12] Thread 11, 29.96 secs, PrimePi(1e13+84e11, 1e13+85e11) = 3273743021   OK
[Apr 12 19:13] Thread  4, 32.45 secs, PrimePi(1e13+37e11, 1e13+38e11) = 3305523133   OK

All tests passed successfully!

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].
  -g, --gpu                  Count primes and prime k-tuplets on a GPU.
                             Falls back to the CPU sieve for small ranges
                             and if no GPU can be initialised.
      --gpu-device=NUM       Use GPU device NUM, as listed by --gpu-info.
      --gpu-info             Print the available GPU devices.
  -n, --nth-prime            Find the nth prime.
                             primesieve 100 -n: finds the 100th prime,
                             primesieve 2 100 -n: finds the 2nd prime > 100.
  -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.
  -S, --stress-test[=MODE]   Run a stress test. The MODE can be either
                             CPU (default) or RAM. The default timeout is 24h.
      --test                 Run various correctness tests (< 1 minute).
  -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.
      --timeout=SEC          Set the stress test timeout in seconds. Supported
                             units of time suffixes: s, m, h, d or y.
                             30 minutes timeout: --timeout 30m

Build instructions

You need to have installed a C++ compiler which supports C++11 (or later) and CMake ≥ 3.9.

cmake .
cmake --build . --parallel
sudo cmake --install .
sudo ldconfig

• Detailed build instructions

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 < 10^6 */
  while ((prime = primesieve_next_prime(&it)) < 1000000)
    printf("%" PRIu64 "\n", prime);

  primesieve_free_iterator(&it);
  return 0;
}

• C API documentation

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 < 10^6
  for (; prime < 1000000; prime = it.next_prime())
    std::cout << prime << std::endl;

  return 0;
}

• C++ API documentation

Bindings for other languages

primesieve natively supports C and C++ and has bindings available for:

Common Lisp:	cl-primesieve
Java:	primesieve-java
Janet:	janet-primesieve
Julia:	PrimeSieve.jl
Lua:	lua-primesieve
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!

Sponsors

Thanks to all current and past sponsors of primesieve! Your donations help me purchase (or rent) the latest CPUs and ensure primesieve runs at maximum performance on them. Your donations also motivate me to continue maintaining primesieve.