Meissel–Lehmer algorithm


The Meissel–Lehmer algorithm is an algorithm that computes the prime-counting function.

Description

The key identity

Given, one may define the following functions: Firstly,
this function measures the set when one has sieved out multiples of the first primes ; that is, is the sequence of prime numbers in increasing order.
We may further split that up with the functions
these measure the set but considers only the numbers that have exactly prime factors. With these, we have
the sum on the right is finite, since numbers have, for instance, prime factors.
The identities
prove that one may compute by computing and,. And this is what the Meissel–Lehmer algorithm does.

Formulae for the ''P''''k''(''x'', ''a'')

For, we get the following formula for :
For, there is a similar expansion.

Expanding ''?''(''x'', ''a'')

Using the formula
may be expanded. Each summand, in turn, may be expanded in the same way, so that a very large alternating sum arises.

Combining the terms

The only thing that remains to be done is evaluating and for certain values of and. This can be done by direct sieving and using the above formulas.

A modern variant

, Victor Miller and Andrew Odlyzko published a realisation of this algorithm which computes in time and space for any. Upon setting, the tree of has leaf nodes.