# Meissel-Lehmer method

### From Polymath1Wiki

The **Meissel-Lehmer method** is a combinatorial method for computing π(*x*) in time/space *x*^{2 / 3 + o(1)}. It is analysed at LMO???

Define an *x*^{1 / 3}-*almost prime* to be an integer less than x not divisible by any prime less than *x*^{1 / 3}; such a number is either a prime, or a product of two primes which are between *x*^{1 / 3} and *x*^{2 / 3}. Each number of the latter form can be written in two ways as the product of a prime p between *x*^{1 / 3} and *x*^{2 / 3}, and a prime between *x*^{1 / 3} and *x* / *p*, except for the squares of primes between *x*^{1 / 3} and *x*^{1 / 2} which only have one such representation. The number π(*x*,*x*^{1 / 3}) of almost primes less than x is thus

- (1)

(ignoring some floor and ceiling functions).

Using the sieve of Erathosthenes, one can compute π(*y*) for all in time/space *x*^{2 / 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 *x*^{1 / 3}-almost primes less than x in time *x*^{2 / 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 *x*^{1 / 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 *x*^{1 / 3}, one can express π(*x*,*x*^{1 / 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*,*x*^{1 / 3}) as required.