快速素数生成器
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 $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 > 232. primesieve uses 8 bytes per sieving prime, in practice its memory usage is about $\pi(\sqrt{n})\times 8$ bytes per thread.
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
# 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
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.
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).
…
Usage: primesieve [START] STOP [OPTION]...
Generate the primes and/or prime k-tuplets inside [START, STOP]
( 100.
-p, --print[=NUM] Print primes or prime k-tuplets, NUM
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;
}
Include the `````` header to use libprimesieve's C++ API.
#include
#include
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;
}
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!
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.
暂无开放 Issues，或尚未同步最近议题。