Computing pi(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko method

Let pi(x) denote the number of primes less than or equal to x. Our aim in this paper is to present some refinements of a combinatorial method for computing single values of pi(x), initiated by the German astronomer Meissel in 1870, extended and simplified by Lehmer in 1959, and improved in 1985 by Lagarias, Miller and Odlyzko. We show that it is possible to compute pi(x) in O(x(2/3)\log(2)x) time and O(x(1/3) log(3) x log log x) space. The algorithm has been implemented and used to compute pi(10(18)).