Primesieve is an educational app dedicated to math scientists and students.
Primesieve comes accompanied by a C++ library that uses a highly optimized implementation of the sieve of Eratosthenes. The main aim of the assembly is to generate prime numbers and prime k-tuplets (twin primes, prime triplets, etc.).
Primesieve uses the segmented sieve of Eratosthenes with wheel factorization also known as Pritchard's segmented wheel sieve. The algorithm has a complexity of O(n) operations and is using O(sqrt(n)) bits of memory.
In 2002 Tomas Oliveira e Silva made an improvement to the segmented sieve of Eratosthenes using linked lists allowing use of segments smaller than sqrt(n) without deteriorating efficiency.
This is important as only small segments that fit into the CPU's L1 or L2 cache provide fast memory access.
Although a few other prime number sieves are known now that are slightly more efficient and use O(n/log log n) operations the segmented wheel sieve (with linked lists) has been the fastest prime number sieve since its discovery in 1981.
Primesieve is cross-platform and it works on Mac OS X, Windows and Linux. Binaries for the Windows and Linux platforms are available on the project's homepage.
Here are some key features of "Primesieve":
· Uses a bit array with 30 numbers per byte for sieving
· Pre-eliminates multiples of small primes
What's New in This Release: [ read full changelog ]
· libprimesieve generates (callback) primes up to 5% faster on little-endian CPUs (x86, x86-64) due to improved endiansafe_cast.h (src/soe).
· The best pre-sieve setting is now automatically chosen at runtime, this speeds up sieving small intervals.
· The Makefile now supports the Solaris OS.
· Updated documentation: README, INSTALL, doc/EXAMPLES, doc/FAQ and doc/LIBPRIMESIEVE. New files: AUTHORS and THANKS.
· Fixed a bug in the primesieve GUI code (doc/BUGS).
· Updated ExpressionParser.h (src/apps/*) to version 2.5.
· Added more example programs: examples/store_primes_in_vector.cpp and examples/nth_prime.cpp.
· Lots of refactoring to make the code easier to understand.
· The undocumented pre-sieve methods have been removed (pre-sieving is now automatically configured at runtime).
· void PrimeSieve::getPreSieve();
· void PrimeSieve::setPreSieve(int);