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