Skip to content

primecount-7.1
Compare
Choose a tag to compare
@kimwalisch kimwalisch released this 14 Aug 08:55
· 1142 commits to master since this release
v7.1
7085111

PrimePi(x) is now computed in O(1) for small values of x < 64 * 240 using a lookup table. primecount's partial sieve function phi(x, a) implementation now uses a compressed lookup table for small values of a. It can compute phi(x, a) in O(1) for a ≤ 8 (previously 6). The improved phi(x, a) also benefits the computation of the hard special leaves which now does more pre-sieving and hence runs slightly faster.

  • Partial-Sieve-Function.md: Description of phi(x, a) algorithm.
  • PhiTiny.cpp: Use compressed phi(x, a) lookup table.
  • phi.cpp: More correct usage of recursive phi(x, a) formula.
  • PiTable.cpp: Add PrimePi(x) lookup table for x < 64 * 240.
  • generate_phi.hpp: More correct usage of recursive phi(x, a) formula.
  • nth_prime.cpp: Cache small primes ≤ 1009.
  • nth_prime.cpp: Improve error handling, n must be ≥ 1.
  • appveyor.yml: Fix debug build.
Assets 3
Loading