# 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)}$.

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 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)$

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^{2/3}$ by the sieve of Eratosthenes, we can store $\pi(y,a)$ for all $a, y \leq x^{2/3}$, to be retrievable in O(1) time. One can then show by induction that $\pi(y,a)$ is computable for larger a,y in time $O_\varepsilon( (ay)^{1+\varepsilon} / x^{2/3} )$ for any $\varepsilon \gt 0$, which gives the $x^{2/3+o(1)}$ algorithm.

[ Note: the above paragraph needs to be checked ]