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.