Skip to content
πŸš€ Fast prime number generator
Branch: master
Clone or download
Latest commit 76d2b77 Apr 20, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
cmake
doc Update version to 7.5 Apr 7, 2019
examples Refactor Apr 23, 2018
include Update version to 7.5 Apr 7, 2019
scripts Fix copyright update Oct 26, 2018
src Use GitHub project URL Apr 3, 2019
test Silence cppcheck warning Dec 2, 2018
.gitignore Ignore all build directories Apr 8, 2018
.travis.yml
BUILD.md Update MSVC build instructions Apr 2, 2019
CMakeLists.txt Update version to 7.5 Apr 7, 2019
COPYING Update year to 2019 Jan 2, 2019
ChangeLog Update Changelog Apr 20, 2019
README.md
appveyor.yml Build libprimesieve as DLL on Windows (#60) Oct 1, 2018
primesieve.pc.in

README.md

primesieve

Build Status Build Status Github Releases

primesieve is a program and C/C++ library that generates primes using a highly optimized sieve of Eratosthenes implementation. It counts the primes below 10^10 in just 0.4 seconds on an Intel Core i7-6700 CPU (4 x 3.4 GHz). primesieve can generate primes and prime k-tuplets up to 2^64.

primesieve windows screenshot

Algorithms

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^32. primesieve uses 8 bytes per sieving prime, hence its memory usage is about bytes per thread.

Installation

The primesieve console application can be installed using your operating system's package manager. You can also download the latest primesieve console and GUI applications from the downloads page.

# Debian, Ubuntu
sudo apt install primesieve

# Homebrew (macOS) or Linuxbrew
brew install primesieve

# Windows using Chocolatey package manager
choco 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[N+], --count[=N+]   Count primes and prime k-tuplets, N <= 6,
                         e.g. -c1 primes, -c2 twins, -c3 triplets, ...
          --cpu-info     Print CPU information
  -d<N>,  --dist=<N>     Sieve the interval [START, START + N]
  -h,     --help         Print this help menu
  -n,     --nth-prime    Calculate the nth prime,
                         e.g. 1 100 -n finds the 1st prime > 100
          --no-status    Turn off the progressing status
  -p[N],  --print[=N]    Print primes or prime k-tuplets, N <= 6,
                         e.g. -p1 primes, -p2 twins, -p3 triplets, ...
  -q,     --quiet        Quiet mode, prints less output
  -s<N>,  --size=<N>     Set the sieve size in KiB, N <= 4096
          --test         Run various sieving tests
  -t<N>,  --threads=<N>  Set the number of threads, N <= 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

C++ API

Below is an example with the most common libprimesieve use cases.

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

int main()
{
  // store the primes below 1000
  std::vector<int> primes;
  primesieve::generate_primes(1000, &primes);

  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;
}

C API

primesieve's functions are exposed as C API via the primesieve.h header.

#include <primesieve.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("%llu\n", prime);

  primesieve_free_iterator(&it);
  return 0;
}

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^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://primesieve.org/primesum.cpp
c++ -O3 -fopenmp primesum.cpp -o primesum -lprimesieve
time ./primesum

Linking against libprimesieve

Unix-like OSes

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

If you have built primesieve yourself then the default installation path is /usr/local/lib which is not part of LD_LIBRARY_PATH on many OSes. Hence 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 primes.cpp /I primesieve\include /link primesieve.lib

CMake support

Since primesieve-6.4 you can easily link against libprimesieve in your CMakeLists.txt:

find_package(primesieve REQUIRED)
target_link_libraries(your_target primesieve::primesieve)

To link against the static libprimesieve use:

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

Bindings for other languages

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

Python: primesieve-python
Perl: perl6-primesieve
Ruby: primesieve-ruby
Rust: primesieve.rs
Haskell: primesieve-haskell

Many thanks to the developers of these bindings!

You can’t perform that action at this time.