The Meissel–Lehmer algorithm (after Ernst Meissel and Derrick Henry Lehmer) is an algorithm that computes exact values of the prime-counting function.
Description The problem of counting the exact number of primes less than or equal to x, without actually listing them all, dates from Legendre. He observed from the Sieve of Eratosthenes that
π ( x ) − π ( x 1 / 2 ) + 1 = ⌊ x ⌋ − ∑ i ⌊ x / p i ⌋ + ∑ i < j ⌊ x / p i p j ⌋ − … {\displaystyle \pi (x)-\pi (x^{1/2})+1=\lfloor x\rfloor -\sum _{i}\lfloor x/p_{i}\rfloor +\sum _{i<j}\lfloor x/p_{i}p_{j}\rfloor -\ldots }
where ⌊x⌋ is the floor function, which denotes the greatest integer less than or equal to x and the pi run over all primes ≤ √x. Since the evaluation of this sum formula becomes more and more complex and confusing for large x, Meissel tried to simplify the counting of the numbers in the Sieve of Eratosthenes. He and Lehmer therefore introduced certain sieve functions, which are detailed below.
Key functions Let p1, p2, …, pn be the first n primes. For a natural number a ≥ 1, define
φ ( x , a ) := | { n ≤ x : p | n ⟹ p > p a } | , {\displaystyle \varphi (x,a):=\left|\left\{n\leq x:p|n\implies p>p_{a}\right\}\right|,}
which counts natural numbers no greater than x with all prime factors greater than pa. Also define for a natural number k,
P k ( x , a ) := | { n ≤ x : n = q 1 q 2 ⋯ q k , with q 1 , … , q k > p a } | , {\displaystyle P_{k}(x,a):=\left|\left\{n\leq x:n=q_{1}q_{2}\cdots q_{k},~{\text{with}}~q_{1},\ldots ,q_{k}>p_{a}\right\}\right|,}
which counts natural numbers no greater than x with exactly k prime factors, all greater than pa. With these, we have
φ ( x , a ) = ∑ k = 0 ∞ P k ( x , a ) , {\displaystyle \varphi (x,a)=\sum _{k=0}^{\infty }P_{k}(x,a),}
where the sum only has finitely many nonzero terms because Pk(x, a) = 0 when pka > x. Using the fact that P0(x, a) = 1 and P1(x, a) = π(x) − a, we get
π ( x ) = φ ( x , a ) + a − 1 − ∑ k = 2 ∞ P k ( x , a ) , {\displaystyle \pi (x)=\varphi (x,a)+a-1-\sum _{k=2}^{\infty }P_{k}(x,a),}
which proves that one may compute π(x) by computing φ(x,a) and Pk(x, a) for k ≥ 2. This is what the Meissel–Lehmer algorithm does.
Formula for Pk(x, a) For k = 2, we get the following formula for Pk(x, a):
… excerpt ends here. Continue reading the full article.
