Skip to content

primecount-5.1
Compare
Choose a tag to compare
@kimwalisch kimwalisch released this 02 Sep 15:14
· 2093 commits to master since this release
v5.1
3c8673e

The memory usage of Xavier Gourdon's algorithm has been reduced from O(x^(1/2)) to O(x^(1/3) * log^3 x). Xavier Gourdon's algorithm is now fully implemented and luckily it scales well up to a very large number of CPU cores. Xavier Gourdon's algorithm is now enabled by default for numbers > 10^7.

  • main.cpp: New options: --AC, --B, --D, --Phi0, --Sigma.
  • SegmentedPiTable.cpp: New PiTable implementation.
  • AC.cpp: Combine the A & C formulas to improve scaling.
  • D4.cpp: Tighter bounds, minor speedup.
  • Sigma.cpp: Reduce initialization overhead.
  • Sieve.cpp: Improved pre-sieving.
  • S2_hard.cpp: Improved pre-sieving.
  • print.cpp: Updated for Gourdon's algorithm.

C++ API Changes

In order to simplify the API the following functions have been removed from the primecount.hpp header:

int64_t pi_deleglise_rivat(int64_t x);
int64_t pi_legendre(int64_t x);
int64_t pi_lehmer(int64_t x);
int64_t pi_lmo(int64_t x);
int64_t pi_meissel(int64_t x);
int64_t pi_primesieve(int64_t x);

You should use pi(x) instead which is an alias for the fastest prime counting function implementation in primecount.

Assets 5
Loading