information:highlighting, quality:corruption, linguistic:voice_change
The Meissel–Lehmer algorithm

In a series of articles published between 1870 and 1885, Ernst Meissel described (and used) a practical combinatorial way of evaluating π (x): Let p, p,…, p be the first n primes and denote by Φ(m, n) the number of natural numbers not greater than m which are divisible by none of the p for any i ≤ n. Then

Given a natural number m, if n = π (√ m) and if μ = π (√ m) − n, then

Using this approach, Meissel computed π (x), for x equal to 5 × 10, 10, 10, and 10.

In 1959, Derrick Henry Lehmer extended and simplified Meissel's method. Define, for real m and for natural numbers n and k, P (m, n) as the number of numbers not greater than m with exactly k prime factors, all greater than p. Furthermore, set P (m, n) = 1. Then

where the sum actually has only finitely many nonzero terms. Let y denote an integer such that √ m ≤ y ≤ √ m, and set n = π (y). Then P (m, n) = π (m) − n and P (m, n) = 0 when k ≥ 3. Therefore,

The computation of P (m, n) can be obtained this way:

where the sum is over prime numbers.

On the other hand, the computation of Φ(m, n) can be done using the following rules:

Using his method and an IBM 701, Lehmer was able to compute the correct value of π (10) and missed the correct value of π (10) by 1.

Further improvements to this method were made by Lagarias, Miller, Odlyzko, Deléglise, and Rivat.