Credits

My thanks to the following people, without whom primecount wouldn’t be what it is today. (Please let me know if I’ve mistakenly omitted anyone.)

• David Baugh
  David was the most extensive user of primecount during early development. He reported numerous bugs and suggested a lot of useful features e.g. backup functionality & standalone flags for all deleglise-rivat formulas. David also broke many world records using primecount e.g. A006880, A006988, A122121, A040014.

• Dana Jacobsen
  Dana explained to me in great detail the optimizations used in his phi(x, a) implementation and also the implementation of the inverse logarithmic integral using Newton’s method.

• Curtis Seizert
  Curtis partially implemented Xavier Gourdon’s combinatorial prime counting algorithm and wrote a paper comparing the Deleglise-Rivat algorithm, Tomás Oliveira e Silva’s version of the Deleglise-Rivat algorithm and Gourdon’s algorithm. This improved my understanding of Gourdon’s algorithm.

• Douglas Staple
  After computing pi(10^26) using his own program Douglas Staple published a paper with his improvements to the Deleglise-Rivat algorithm. I use Douglas Staple’s improvements for the computation of the ordinary leaves and the multi-threading of the hard special leaves.

• Christian Bau
  Christian Bau wrote the first open source implementation of the extended Meissel-Lehmer prime counting algorithm in 2003. I use Christian’s FactorTable idea to reduce the memory usage and also his fast integer division trick (use 32-bit instead of 64-bit whenever possible).

• Dennis Mitchell
  Dennis wrote a highly optimized implementation (in 2016) of the meissel prime counting algorithm which was faster than primecount for x <= 10¹⁰. Dennis’s implementation replaced integer division by multiplication & bit shifts. After studying his implementation I also implemented this trick in primecount.

• ridiculousfish
  primecount uses ridiculousfish’s libdivide library to replace integer division by multiplication & bit shifts. This optimization speeds up the computation of the easy special leaves by about 40%. ridiculousfish added a branchfree divider to libdivide specifically for primecount.