A method for computing the prime counting function. Define the function
where is the floor function and the are the binary digits (0 or 1) in
Legendre's formula can then be written
The first few values of are
Mapes' method takes time , which is slightly faster than the Lehmer-Schur method.
More things to try:
Weisstein, Eric W. "Mapes' Method." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MapesMethod.html