Open main menu

The Meissel–Lehmer algorithm (after Ernst Meissel and Derrick Henry Lehmer) is an algorithm that computes the prime-counting function.[1][2]

Contents

DescriptionEdit

The key identityEdit

Given  , one may define the following functions: Firstly,

 

this function measures the set   (closed interval) when one has sieved out multiples of the first   primes   (including these primes themselves); 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 (this is well-defined by the fundamental theorem of arithmetic). 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 Pk(x, a)Edit

For  , we get the following formula for  :

 

For  , there is a similar expansion.[2]

Expanding 𝜑(x, a)Edit

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 termsEdit

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 variantEdit

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

ReferencesEdit

  1. ^ a b c Lagarias, Jeffrey; Miller, Victor; Odlyzko, Andrew (April 11, 1985). "Computing  : The Meissel–Lehmer method" (PDF). Mathematics of Computation. 44 (170): 537–560. doi:10.1090/S0025-5718-1985-0777285-5. Retrieved September 13, 2016.
  2. ^ a b Lehmer, Derrick Henry (April 1, 1958). "ON THE EXACT NUMBER OF PRIMES LESS THAN A GIVEN LIMIT". Illinois J. Math. 3 (3): 381–388. Retrieved February 1, 2017.