The Meissel-Lehmer method is a combinatorial method for computing π(x) in time/space x2 / 3 + o(1). It is analysed at LMO???
Define an x1 / 3-almost prime to be an integer less than x not divisible by any prime less than x1 / 3; such a number is either a prime, or a product of two primes which are between x1 / 3 and x2 / 3. Each number of the latter form can be written in two ways as the product of a prime p between x1 / 3 and x2 / 3, and a prime between x1 / 3 and x / p, except for the squares of primes between x1 / 3 and x1 / 2 which only have one such representation. The number π(x,x1 / 3) of almost primes less than x is thus
(ignoring some floor and ceiling functions).
Using the sieve of Erathosthenes, one can compute π(y) for all in time/space x2 / 3 + o(1), so every expression in (1) is computable in this time except for π(x). So it will suffice to compute the number of x1 / 3-almost primes less than x in time x2 / 3 + o(1).
If we let π(x,a) denote the number of a-almost primes less than x (i.e. the number of integers less than x not divisible by any integer between 2 and a), we have the recurrence
- π(x,a) = π(x,a − 1) − π(x / a,a) (2)
which reflects the basic fact that the a-1-almost primes are the union of the a-almost primes, and the a-1-almost primes multiplied by a. On the other hand, by factoring all the numbers up to x1 / 3 by the sieve of Eratosthenes, we can store π(y,a) for all , to be retrievable in O(1) time. Meanwhile, by recursively expanding out (2) until the x parameter dips below x1 / 3, one can express π(x,x1 / 3) as an alternating sum of various π(y,b) with , with each π(y,b) occurring at most once; summing using the stored values then gives π(x,x1 / 3) as required.