Meissel-Lehmer method

From Polymath1Wiki

Jump to: navigation, search

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

 \pi(x) - \pi(x^{1/3}) +  \frac{1}{2} \sum_{x^{1/3} \leq p \leq x^{2/3}} [\pi( x/p ) - \pi(x^{1/3})] + \frac{1}{2} (\pi(x^{1/2})-\pi(x^{1/3})) (1)

(ignoring some floor and ceiling functions).

Using the sieve of Erathosthenes, one can compute π(y) for all y \leq x^{2/3} 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 a, y \leq x^{1/3}, 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 y,b \leq x^{1/3}, with each π(y,b) occurring at most once; summing using the stored values then gives π(x,x1 / 3) as required.

Personal tools