Mapes' Method

A method for computing the prime counting function. Define the function

(1)

where  is the floor function and the  are the binary digits (0 or 1) in

(2)

Legendre's formula can then be written

(3)

The first few values of  are

			(4)
			(5)
			(6)
			(7)
			(8)
			(9)
			(10)
			(11)

Mapes' method takes time , which is slightly faster than the Lehmer-Schur method.

REFERENCES:

Mapes, D. C. "Fast Method for Computing the Number of Primes Less than a Given Limit." Math. Comput. 17, 179-185, 1963.

Riesel, H. "Mapes' Method." Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, p. 23, 1994.