kimwalisch / Primesieve
Labels
Projects that are alternatives of or similar to Primesieve
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 264.
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 > 232. primesieve uses 8 bytes per sieving prime, hence its memory usage is about bytes per thread.
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: | choco install primesieve |
macOS: | brew install primesieve |
Arch Linux: | sudo pacman -S primesieve |
Debian/Ubuntu: | sudo apt install primesieve |
Fedora: | sudo dnf install primesieve |
openSUSE: | sudo zypper install primesieve |
FreeBSD: | pkg 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 <= 4096.
By default primesieve uses a sieve size that
matches your CPU's L1 cache size or half of
your CPU's L2 cache size (per core).
--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
C++ API
Below is a C++ example with the most common libprimesieve use case.
#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;
}
C API
libprimesieve'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;
}
libprimesieve performance tips
-
primesieve::iterator::next_prime()
runs up to 2x faster and uses only half as much memory asprev_prime()
. Oftentimes algorithms that iterate over primes usingprev_prime()
can be rewritten usingnext_prime()
which improves performance in most cases. -
primesieve::iterator
is single-threaded. See the multi-threading section for how to parallelize an algorithm using multipleprimesieve::iterator
objects. -
The
primesieve::iterator
constructor and theprimesieve::iterator::skipto()
method take an optionalstop_hint
parameter that can provide a significant speedup if the sieving distance is relatively small e.g. < sqrt(start). Ifstop_hint
is setprimesieve::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 aprimesieve::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 ≤ 1010 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 may 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:
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!