Editing Prime-counting function (section)

=== The Meissel–Lehmer algorithm ===

{{main|Meissel–Lehmer algorithm}}

In a series of articles published between 1870 and 1885, [[Ernst Meissel]] described (and used) a practical combinatorial way of evaluating {{math|''π''(''x'')}}: Let {{math|''p''<sub>1</sub>, ''p''<sub>2</sub>,…, ''p<sub>n</sub>''}} be the first {{mvar|n}} primes and denote by {{math|Φ(''m'',''n'')}} the number of natural numbers not greater than {{mvar|m}} which are divisible by none of the {{mvar|p<sub>i</sub>}} for any {{math|''i'' ≤ ''n''}}. Then

: <math>\Phi(m,n)=\Phi(m,n-1)-\Phi\left(\frac m {p_n},n-1\right).</math>

Given a natural number {{mvar|m}}, if {{math|''n'' {{=}} ''π''({{sqrt|''m''|3}})}} and if {{math|''μ'' {{=}} ''π''({{sqrt|''m''}}) − ''n''}}, then

:<math>\pi(m) = \Phi(m,n)+n(\mu+1)+\frac{\mu^2-\mu} 2 - 1 - \sum_{k=1}^\mu\pi\left(\frac m {p_{n+k}}\right) .</math>

Using this approach, Meissel computed {{math|''π''(''x'')}}, for {{mvar|x}} equal to {{val|5e5}}, 10<sup>6</sup>, 10<sup>7</sup>, and 10<sup>8</sup>.

In 1959, [[Derrick Henry Lehmer]] extended and simplified Meissel's method. Define, for real {{mvar|m}} and for natural numbers {{mvar|n}} and {{mvar|k}}, {{math|''P<sub>k</sub>''(''m'',''n'')}} as the number of numbers not greater than {{mvar|m}} with exactly {{mvar|k}} prime factors, all greater than {{mvar|p<sub>n</sub>}}. Furthermore, set {{math|''P''<sub>0</sub>(''m'',''n'') {{=}} 1}}. Then

:<math>\Phi(m,n) = \sum_{k=0}^{+\infty} P_k(m,n)</math>

where the sum actually has only finitely many nonzero terms. Let {{mvar|y}} denote an integer such that {{math|{{sqrt|''m''|3}} ≤ ''y'' ≤ {{sqrt|''m''}}}}, and set {{math|''n'' {{=}} ''π''(''y'')}}. Then {{math|''P''<sub>1</sub>(''m'',''n'') {{=}} ''π''(''m'') − ''n''}} and {{math|''P<sub>k</sub>''(''m'',''n'') {{=}} 0}} when {{math|''k'' ≥ 3}}. Therefore,

:<math>\pi(m) = \Phi(m,n) + n - 1 - P_2(m,n)</math>

The computation of {{math|''P''<sub>2</sub>(''m'',''n'')}} can be obtained this way:

:<math>P_2(m,n) = \sum_{y < p \le \sqrt{m} } \left( \pi \left( \frac m p \right) - \pi(p) + 1\right)</math>

where the sum is over prime numbers.

On the other hand, the computation of {{math|Φ(''m'',''n'')}} can be done using the following rules:

#<math>\Phi(m,0) = \lfloor m\rfloor</math>
#<math>\Phi(m,b) = \Phi(m,b-1) - \Phi\left(\frac m{p_b},b-1\right)</math>

Using his method and an [[IBM 701]], Lehmer was able to compute the correct value of {{math|''π''(10<sup>9</sup>)}} and missed the correct value of {{math|''π''(10<sup>10</sup>)}} by 1.<ref name="lehmer">{{cite journal |last=Lehmer |first=Derrick Henry |author-link=D. H. Lehmer |date=1 April 1958 |title=On the exact number of primes less than a given limit |journal=Illinois J. Math. |volume=3 |issue=3 |pages=381–388 |url=https://projecteuclid.org/download/pdf_1/euclid.ijm/1255455259 |access-date=1 February 2017 }}</ref>

Further improvements to this method were made by Lagarias, Miller, Odlyzko, Deléglise, and Rivat.<ref name="pix_comp">{{cite journal |author1 = Deléglise, Marc |author2 = Rivat, Joel |date=January 1996 |title=Computing {{math|''π''(''x'')}}: The Meissel, Lehmer, Lagarias, Miller, Odlyzko method  |journal=Mathematics of Computation |volume=65 |issue=213 |pages=235–245 |doi = 10.1090/S0025-5718-96-00674-6 |doi-access=free |url=https://www.ams.org/mcom/1996-65-213/S0025-5718-96-00674-6/S0025-5718-96-00674-6.pdf }}</ref>