# Meissel-Lehmer method

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

The Meissel-Lehmer method is a combinatorial method for computing $\pi(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 $\pi(x,x^{1/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 $\pi(y)$ for all $y \leq x^{2/3}$ in time/space $x^{2/3+o(1)}$, so every expression in (1) is computable in this time except for $\pi(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 $\pi(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

$\pi(x,a) = \pi(x,a-1) - \pi(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 $\pi(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 $x^{1/3}$, one can express $\pi(x,x^{1/3})$ as an alternating sum of various $\pi(y,b)$ with $y,b \leq x^{1/3}$, with each $\pi(y,b)$ occurring at most once; summing using the stored values then gives $\pi(x,x^{1/3})$ as required.