Primesieve

is easier to use and that will not break binary compatibility with
every new release. The new API is not backwards compatible but porting
your code to the new API should be done quickly. You can explore
primesieve's new API online at: http://primesieve.org/api.

I bought a domain for primesieve and moved primesieve's repository
from Google Code (SVN) to GitHub (git):

http://primesieve.org
http://github.com/kimwalisch/primesieve

Other changes:

1. New primesieve::iterator class that provides next_prime() and
previous_prime() methods.
2. ParallelPrimeSieve now uses multi-threading by default, it does not
care about arithmetic order anymore. Please do not use
ParallelPrimeSieve directly anymore instead use the new API.
3. Renamed src/soe to src/primesieve.
4. Renamed PrimeSieveCallback<T> class to Callback<T>.
5. Moved most header files to include/primesieve.

Changes in version 4.4, 19/09/2013
==================================

This is a minor release whose sole purpose is to fix a bug in the
Makefile which is required for integrating primesieve into
Sage (http://www.sagemath.org).

1. Fixed the following bug:
$ make shared && make install PREFIX=/user-path
2. PrimeSieve does not throw an exception anymore if (start > stop)
instead it simply ignores the invalid input.
3. `make SHARED=yes` has been deprecated, use `make shared` instead.

Changes in version 4.3, 05/07/2013
==================================

This release improves primesieve as a library and adds an algorithm
to find the nth prime. The API of primesieve 4.3 is backwards
compatible but the ABI is not (you must recompile your application if
you want to link against a shared libprimesieve 4.3).

1. Support for storing primes in C++ vectors:
PrimeSieve::generatePrimes (start, stop, std::vector<T>*);
PrimeSieve::generate_N_Primes(start, n, std::vector<T>*);
2. New algorithm to find the nth prime:
PrimeSieve::nthPrime(n);
PrimeSieve::nthPrime(start, n);
3. The Makefiles now build primesieve and a static libprimesieve by
default. A shared libprimesieve can be built using:
$ make shared
4. Added a <primesieve/soe/stop_primesieve.h> header for
this commonly used exception to abort sieving.
5. Updated the documentation files: INSTALL, doc/API, doc/EXAMPLES
doc/LIBPRIMESIEVE, doc/FAQ
6. Updated the source code examples in ./examples.
7. Added the scripts/install_primesieve.sh shell script that
automatically downloads, builds and installs the latest primesieve
and libprimesieve version.

Changes in version 4.2, 10/03/2013
==================================

1. libprimesieve generates (callback) primes up to 5% faster on
little-endian CPUs (x86, x86-64) due to improved
endiansafe_cast.h (src/soe).
2. The best pre-sieve setting is now automatically chosen at
runtime, this speeds up sieving small intervals.
3. The Makefile now supports the Solaris OS.
4. Updated documentation: README, INSTALL, doc/EXAMPLES, doc/FAQ
and doc/LIBPRIMESIEVE. New files: AUTHORS and THANKS.
5. Fixed a bug in the primesieve GUI code (doc/BUGS).
6. Updated ExpressionParser.h (src/apps/*) to version 2.5.
7. Added more example programs: examples/store_primes_in_vector.cpp
and examples/nth_prime.cpp.
8. Lots of refactoring to make the code easier to understand.

API changes
-----------

The undocumented pre-sieve methods have been removed
(pre-sieving is now automatically configured at runtime).

void PrimeSieve::getPreSieve();
void PrimeSieve::setPreSieve(int);

Changes in version 4.1, 12/01/2013
==================================

1. New PrimeSieveCallback interface class that simplifies prime
number generation with classes, see doc/EXAMPLES.
2. The primesieve console (terminal) application now supports
GNU-style long options e.g. --size=256.
3. Fixed a bug (for sizeof(int) > 4) in the bit population count
algorithm, read BUGS file.
4. Updated files: README, INSTALL, doc/EXAMPLES.
5. The Makefile now uses the system's default C++ compiler instead
of GNU g++ which makes it more portable.
6. The primesieve_error class has been moved into its own file
src/soe/primesieve_error.h (previously PrimeSieve.h).

API changes
-----------

The following two overly complex PrimeSieve methods have been
removed:

void PrimeSieve::generatePrimes(uint32_t start, uint32_t stop, void (*)(uint32_t, void*), void*);
void PrimeSieve::generatePrimes(uint64_t start, uint64_t stop, void (*)(uint64_t, void*), void*);

They are replaced by the following two new methods that greatly
simplify prime number generation with classes, please refer
to doc/EXAMPLES for more information.

void PrimeSieve::generatePrimes(uint32_t start, uint32_t stop, PrimeSieveCallback<uint32_t>*);
void PrimeSieve::generatePrimes(uint32_t start, uint32_t stop, PrimeSieveCallback<uint64_t>*);

Changes in version 4.0, 18/10/2012
==================================

changes are documented further down.

1. Added support for OpenMP 2.*, useful for compilers that do
not support OpenMP >= 3.0, e.g. MSVC, Apple g++.
2. New examples directory with 12 simple example programs.
3. New doc/API file that lists the public member functions of the
PrimeSieve and ParallelPrimeSieve C++ classes.
4. The Makefile is now POSIX compatible, it works with any POSIX
shell e.g. sh, bash, ash, ksh, zsh, ...
5. The Makefile now supports MinGW (with MSYS) and Cygwin.
6. Fixed a shared libprimesieve bug (read doc/BUGS).
7. Up to 10 percent faster prime number generation due to new
internal 64-bit getNextPrime() (previously 32-bit).
8. New unsynchronized ParallelPrimeSieve::generatePrimes() method
that calls back primes in parallel (read EXAMPLES).
9. Faster thread synchronization in ParallelPrimeSieve, replaced slow
OpenMP critical directive with faster omp_test_lock().
10. Optimized prime k-tuplet (twin primes, ...) counting for
out-of-order CPUs (src/soe/PrimeNumberFinder.cpp).
11. New primesieve_error() exception used for all exceptions within
PrimeSieve and ParallelPrimeSieve (read EXAMPLES).
12. New pre-sieve code (src/soe/PreSieve.cpp).
13. Ported the primesieve GUI application from Qt 4 to Qt 5.

API changes
-----------

The PrimeSieve 3.* count methods:

uint64_t getPrimeCount(uint64_t start, uint64_t stop);
uint64_t getTwinCount (uint64_t start, uint64_t stop);
...

Have been renamed to:

uint64_t countPrimes (uint64_t start, uint64_t stop);
uint64_t countTwins (uint64_t start, uint64_t stop);
uint64_t countTriplets (uint64_t start, uint64_t stop);
uint64_t countQuadruplets(uint64_t start, uint64_t stop);
uint64_t countQuintuplets(uint64_t start, uint64_t stop);
uint64_t countSextuplets (uint64_t start, uint64_t stop);
uint64_t countSeptuplets (uint64_t start, uint64_t stop);

Changes in version 3.8, 13/07/2012
==================================

1. Improved OOP design of WheelFactorization.h.
2. Minor speed up for big sieving primes ~2% (src/soe/EratBig.cpp),
reduced the number of operations in the main sieving loop.
3. Minor speed up for small sieving primes ~3% (src/soe/EraSmall.cpp),
new inner sieving loop without instruction dependencies that uses
only 12 asm instructions (previously 16).
4. Improved OpenMP load balance in src/soe/ParallelPrimeSieve.cpp.
5. Improved code readability of EratSmall.cpp, EratMedium.cpp,
EratBig.cpp, Erat.cpp and others.
6. The Makefile now automatically detects the CPU's L1 data cache
size on Unix-like OSes (Linux, Mac OS X).
7. Renamed ./docs to ./doc
8. Revised README.txt, added 7. Motivation.
9. Updated INSTALL, LIBPRIMESIEVE and EXAMPLES.
10. Added version defines to PrimeSieve.h, e.g. for this release:

define PRIMESIEVE_VERSION "3.8"
define PRIMESIEVE_MAJOR_VERSION 3
define PRIMESIEVE_MINOR_VERSION 8
define PRIMESIEVE_YEAR 2012

Changes in version 3.7, 31/05/2012
==================================

1. More aggressive inlining (*-inline.h), up to 10 percent faster
prime number generation, up to 20 percent faster initialization.
2. Reduced header file dependencies, libprimesieve now only depends on
PrimeSieve.h or ParallelPrimeSieve.h (and PrimeSieve.h).
3. Updated Makefiles.
4. New template imath.h functions: isqrt(), ilog2(), isPow2(), ...
isqrt() has been rewritten using Newton's algorithm in order to
avoid rounding errors of (int)sqrt((double)n) if n > 10^15.
5. New internal Erat::getNextPrime(...) member function.
6. Replaced old C-style comments with C++ comments.
7. Updated ExpressionParser to version 2.2.
8. uin32_t has been replaced by uint_t in src/soe/*.
9. New int API for PrimeSieve and ParallelPrimeSieve objects, getters
and setters now use int instead of uint32_t.
10. Updated documentation files: README, INSTALL, LIBPRIMESIEVE,
EXAMPLES, VALGRIND, TODO, BUGS.

Changes in version 3.6, 22/04/2012
==================================

1. Improved code readability and updated source code documentation
(src/soe directory).
2. Removed unused source code. The deprecated API of
PrimeSieve <= 3.4 is not supported anymore, use
PrimeSieve::getStart() instead of PrimeSieve::getStartNumber() ...
The file EXAMPLES contains the up-to-date API.
3. src/soe/EratSmall.cpp has been enhanced to better take advantage of
Instruction-Level Parallelism.

Changes in version 3.5, 07/02/2012
==================================

1. Bug fix for big-endian CPUs (PowerPC, SPARC), see docs/BUGS.
2. The GNU Makefile now provides an option to build primesieve as
a shared library e.g. `make lib SHARED=yes`.
3. I have rewritten the main documentation files docs/LIBPRIMESIEVE
and docs/EXAMPLES.
4. I have added convenience functions to the PrimeSieve class:

void printPrimes (uint64_t start, uint64_t stop);
void printTwins (uint64_t start, uint64_t stop);
void printTriplets (uint64_t start, uint64_t stop);
void printQuadruplets(uint64_t start, uint64_t stop);
void printQuintuplets(uint64_t start, uint64_t stop);
void printSextuplets (uint64_t start, uint64_t stop);
void printSeptuplets (uint64_t start, uint64_t stop);

uint64_t getPrimeCount (uint64_t start, uint64_t stop);
uint64_t getTwinCount (uint64_t start, uint64_t stop);
uint64_t getTripletCount (uint64_t start, uint64_t stop);
uint64_t getQuadrupletCount(uint64_t start, uint64_t stop);
uint64_t getQuintupletCount(uint64_t start, uint64_t stop);
uint64_t getSextupletCount (uint64_t start, uint64_t stop);
uint64_t getSeptupletCount (uint64_t start, uint64_t stop);

void sieve(uint64_t start, uint64_t stop);
void sieve(uint64_t start, uint64_t stop, uint32_t flags);
void sieve();

(previously OpenMP 2.0). The new OpenMP code is more elegant and
scales better when lots of threads (> 32) are used.
Compiler notes:
OpenMP is now disabled by default for the Microsoft Visual C++
compiler as it currently only supports OpenMP 2.0. Some compilers
e.g. g++ 4.2 even build primesieve with OpenMP <= 2.5 but the
resulting binary miscalculates when sieving > 2^63.
6. Helper classes and functions within src/soe are now defined in the
the newly introduced soe namespace. This makes PrimeSieve more
usable as a library.
7. The header file src/soe/defs.h has been renamed to config.h and its
code readability has been improved.
8. The code of src/console/test.cpp has been simplified.

Changes in version 3.4, 05/01/2012
==================================

1. I implemented a new algorithm for medium sieving primes that is up
to 20 percent faster on todays out-of-order CPUs,
see src/soe/EratMedium.cpp.
2. I adapted the constants in defs.h due to the new EratMedium
algorithm, the maximum sieveSize is now 4096 kilobytes (previously
2048 kilobytes).
3. I revised the Makefiles and INSTALL file.
4. Added docs/LIBPRIMESIEVE and updated README and
docs/EXAMPLES.

Changes in version 3.3, 19/12/2011
==================================

1. Minor optimizations in src/soe/EratBig.cpp (2% speed up).
2. Improved code readability and documentation of
src/soe/ParallelPrimeSieve.cpp.
3. The sieveSize must be <= 2048 kilobytes now (previously 8192), this
makes the WheelFactorization.h & EratBase.h code easier to
understand.

Changes in version 3.2, 13/11/2011
==================================

1. Fixed a bug in src/soe/ParallelPrimeSieve.cpp, see ../docs/BUGS.
2. Added 32-bit prime number generation methods to PrimeSieve.
3. Added a PrimeSieve::cancel_sieving exception that allows to cancel
sieving at run time (see docs/EXAMPLES).
4. ParallelPrimeSieve is now able to generate prime numbers using
multiple threads (previously only multi-threaded counting).
5. The code readability and documentation of WheelFactorization.h/.cpp
has been improved (e.g. renamed sieveIndex to multipleIndex).
6. PreSieve now initializes its preSieved_ array using a 2nd wheel
(modulo 6), up to 40 percent faster.
7. I introduced a 'loopLimit' variable in EratSmall that saves some
calculations and reduces the code size.
8. Added a testFlags(uint32_t) convenience function to PrimeSieve.
9. EratMedium has been simplified, it runs faster than v. 3.1 using
Intel C++ 12.0 but slightly slower with most other compilers.

Changes in version 3.1, 24/10/2011
==================================

1. EratBig::sieve(uint8_t*) now processes multiple sieving primes per
iteration, I measured a speed up of about 6 percent near 1E18.
2. STL containers are now used instead of dynamic memory allocation in
Erat(Small|Medium) which improves multi-threading performance ~ 3%.
3. The Bucket data structure (WheelFactorization.h) has been modified
and it performs well now with more compilers.
4. EratMedium has been simplifed, the new code is far easier to
understand and it is faster with the GNU g++ compiler.
5. Fixed an integer overflow bug in EratMedium.cpp (see BUGS file).
6. The -test option (primesieve console) has been reviewed.
7. I improved the code readability and code documentation, the README
and INSTALL files have also been revised.

Changes in version 3.0, 09/07/2011
==================================

1. The source code is now licensed under the New BSD License
(previously GPL).
2. The source code is now standard C++03 and ISO C99 (stdint.h), i.e.
I removed all compiler intrinsics and built-in functions:
80386 BSF, cpuid, SSE4.2 POPCNT.
3. The thread scheduling of ParallelPrimeSieve has been improved,
10 percent speed up.
4. Prime numbers are now generated using bitScanForward() instead of
lookup tables, 10 percent speed up.
5. Implemented a fast bit population count function, see
popcount_lauradoux() in bithacks.h.
6. Revised the option handling in the console version of primesieve,
added two new options: -o<OFFSET> and -r<PRE-SIEVE>
7. README has been rewritten from scratch.
8. Improved the code readability and revised the comments of the sieve
of Eratosthenes implementation.
9. ResetSieve has been renamed to PreSieve.

Changes in version 2.2, 26/05/2011
==================================

1. Added the file docs/EXAMPLES which shows how to use
PrimeSieve and ParallelPrimeSieve objects.
2. Fixed 4 minor bugs (see BUGS).
3. 10% initialization speedup due to enhancement in
ModuloWheel::setWheelPrime(uint64_t, uint32_t*, uint32_t*, uint32_t*)
4. Added prime number generation functions and a convenience function
to count prime numbers to PrimeSieve.
5. The thread interface of ParallelPrimeSieve has been simplified.
6. The code now compiles and runs with the sunCC compiler.
7. The code readability has been improved.
8. The documentation has been updated.

Changes in version 2.1, 11/04/2011
==================================

1. Fixed a start number bug (read doc/BUGS).
2. Now supports integer arithmetic expressions as number input.
3. Uses OpenMP instead of processes.
4. Added qt-gui/README file.
5. Fixed a bug in the Makefile (clang++ compiler).
6. Updated the README file.

Changes in version 2.0, 15/02/2011
==================================

1. Added soe/ParallelPrimeSieve.cpp which counts primes in parallel
using OpenMP.
2. Added an arithmetic expression parser (./expr) to ease number input.
3. Added a test suite to the console version of primesieve
(option: -test) which runs various correctness tests.
4. The console version has been reviewed and is first released.
5. Fixed a minor bug in soe/PrimeNumberFinder.cpp which counts and
prints the prime preceding the start number (see BUGS file).
6. Improved the memory pool of soe/EratBig.cpp, primesieve 1.0 ran
into trouble when sieving near 2^64.
7. Makefile modified to better support GCC compatible compilers,
e.g. make CXX=x86_64-w64-mingw32-g++