# Prime-counting function

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Prime-counting_function
> Markdown URL: https://mediated.wiki/source/Prime-counting_function.md
> Source: https://en.wikipedia.org/wiki/Prime-counting_function
> Source revision: 1328904428
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{short description|Function representing the number of primes less than or equal to a given number}}
{{Redirect|Π(x)|the variant of the gamma function|Gamma function#Pi function}} 
{{log(x)}}
thumb|right|400px|The values of {{math|''π''(''n'')}} for the first 60 positive integers

In [mathematics](/source/mathematics), the '''prime-counting function''' is the [function](/source/Function_(mathematics)) counting the number of [prime number](/source/prime_number)s less than or equal to some [real number](/source/real_number) {{mvar|x}}.<ref name="Bach">{{cite book |first=Eric |last=Bach |author2=Shallit, Jeffrey |year=1996 |title=Algorithmic Number Theory |publisher=MIT Press |isbn=0-262-02405-5 |pages=volume 1 page 234 section 8.8 |no-pp=true}}</ref><ref name="mathworld_pcf">{{MathWorld |title=Prime Counting Function |urlname=PrimeCountingFunction}}</ref> It is denoted by {{math|''π''(''x'')}} (unrelated to the [number {{pi}}](/source/pi)).

A symmetric variant seen sometimes is {{math|''π''<sub>0</sub>(''x'')}}, which is equal to {{math|''π''(''x'') − {{frac|1|2}}}} if {{mvar|x}} is exactly a prime number, and equal to {{math|''π''(''x'')}} otherwise.  That is, the number of prime numbers less than {{mvar|x}}, plus half if {{mvar|x}} equals a prime.

==Growth rate==
{{main|Prime number theorem}}
Of great interest in [number theory](/source/number_theory) is the [growth rate](/source/Asymptotic_analysis) of the prime-counting function.<ref name="Caldwell">{{cite web | publisher=Chris K. Caldwell | title=How many primes are there? | url=http://primes.utm.edu/howmany.shtml | access-date=2008-12-02 | archive-date=2012-10-15 | archive-url=https://web.archive.org/web/20121015002415/http://primes.utm.edu/howmany.shtml | url-status=dead }}</ref><ref name="Dickson">{{cite book |author-link=L. E. Dickson| first=Leonard Eugene | last=Dickson | year=2005 | title=History of the Theory of Numbers, Vol. I: Divisibility and Primality | publisher=Dover Publications | isbn=0-486-44232-2}}</ref> It was [conjecture](/source/conjecture)d in the end of the 18th century by [Gauss](/source/Carl_Friedrich_Gauss) and by [Legendre](/source/Adrien-Marie_Legendre) to be approximately
<math display=block> \frac{x}{\log x} </math>
where {{math|log}} is the [natural logarithm](/source/natural_logarithm), in the sense that
<math display=block>\lim_{x\rightarrow\infty} \frac{\pi(x)}{x/\log x}=1. </math>
This statement is the [prime number theorem](/source/prime_number_theorem). An equivalent statement is
<math display=block>\lim_{x\rightarrow\infty}\frac{\pi(x)}{\operatorname{li}(x)}=1</math>
where {{math|li}} is the [logarithmic integral](/source/logarithmic_integral) function. The prime number theorem was first proved in 1896 by [Jacques Hadamard](/source/Jacques_Hadamard) and by [Charles de la Vallée Poussin](/source/Charles_Jean_de_la_Vall%C3%A9e-Poussin) independently, using properties of the [Riemann zeta function](/source/Riemann_zeta_function) introduced by [Riemann](/source/Bernhard_Riemann) in 1859. Proofs of the prime number theorem not using the zeta function or [complex analysis](/source/complex_analysis) were found around 1948 by [Atle Selberg](/source/Atle_Selberg) and by [Paul Erdős](/source/Paul_Erd%C5%91s) (for the most part independently).<ref name="Ireland">{{cite book | first=Kenneth | last=Ireland |author2=Rosen, Michael | year=1998 | title=A Classical Introduction to Modern Number Theory  | edition=Second | publisher=Springer | isbn=0-387-97329-X }}</ref>

===More precise estimates===
In 1899, [de la Vallée Poussin](/source/Charles_Jean_de_la_Vall%C3%A9e_Poussin) proved that
<ref>See also Theorem 23 of {{cite book |author = A. E. Ingham |author-link = Albert Ingham |title = The Distribution of Prime Numbers |date=2000 |publisher = Cambridge University Press |isbn=0-521-39789-8}}</ref>
<math display=block>\pi(x) = \operatorname{li} (x) + O \left(x e^{-a\sqrt{\log x}}\right) \quad\text{as } x \to \infty</math>
for some positive constant {{mvar|a}}. Here, {{math|''O''(...)}} is the [big {{mvar|O}} notation](/source/big_O_notation).

More precise estimates of {{math|''π''(''x'')}} are now known. For example, in 2002, [Kevin Ford](/source/Kevin_Ford_(mathematician)) proved that<ref name="Ford">{{cite journal |author=Kevin Ford |title=Vinogradov's Integral and Bounds for the Riemann Zeta Function |journal=Proc. London Math. Soc. |date=November 2002 |volume=85 |issue=3 |pages=565–633 |url=https://faculty.math.illinois.edu/~ford/wwwpapers/zetabd.pdf |doi=10.1112/S0024611502013655 |arxiv=1910.08209 |s2cid=121144007 |archive-date=2022-02-01 |access-date=2020-02-05 |archive-url=https://web.archive.org/web/20220201134152/https://faculty.math.illinois.edu/~ford/wwwpapers/zetabd.pdf |url-status=dead }}</ref>
<math display=block>\pi(x) = \operatorname{li} (x) + O \left(x \exp \left( -0.2098(\log x)^{3/5} (\log \log x)^{-1/5} \right) \right).</math>

Mossinghoff and [Trudgian](/source/Timothy_Trudgian) proved<ref>{{cite journal | first1 = Michael J. | last1 = Mossinghoff  | first2 = Timothy S. | last2 = Trudgian | author2-link=Timothy Trudgian| title = Nonnegative trigonometric polynomials and a zero-free region for the Riemann zeta-function | journal = J. Number Theory | volume = 157 | year = 2015 | pages = 329–349 | arxiv = 1410.3926 | doi = 10.1016/J.JNT.2015.05.010| s2cid = 117968965 }}</ref> an explicit upper bound for the difference between {{math|''π''(''x'')}} and {{math|li(''x'')}}:
<math display=block>\bigl| \pi(x) - \operatorname{li}(x) \bigr| \le 0.2593 \frac{x}{(\log x)^{3/4}} \exp \left( -\sqrt{ \frac{\log x}{6.315} } \right) \quad \text{for } x \ge 229.</math>

For values of {{mvar|x}} that are not unreasonably large, {{math|li(''x'')}} is greater than {{math|''π''(''x'')}}. However, {{math|''π''(''x'') − li(''x'')}} is known to change sign infinitely many times. For a discussion of this, see [Skewes' number](/source/Skewes'_number).

===Exact form===

For {{math|''x'' > 1}} let {{math|''π''<sub>0</sub>(''x'') {{=}} ''π''(''x'') − {{sfrac|1|2}}}} when {{mvar|x}} is a prime number, and {{math|''π''<sub>0</sub>(''x'') {{=}} ''π''(''x'')}} otherwise. [Bernhard Riemann](/source/Bernhard_Riemann), in his work ''[On the Number of Primes Less Than a Given Magnitude](/source/On_the_Number_of_Primes_Less_Than_a_Given_Magnitude)'', proved that {{math|''π''<sub>0</sub>(''x'')}} is equal to<ref>{{Cite web|url=http://ism.uqam.ca/~ism/pdf/Hutama-scientific%20report.pdf|title=Implementation of Riemann's Explicit Formula for Rational and Gaussian Primes in Sage|last=Hutama|first=Daniel|date=2017|website=Institut des sciences mathématiques|access-date=2021-07-31|archive-date=2024-01-27|archive-url=https://web.archive.org/web/20240127053553/http://ism.uqam.ca/~ism/pdf/Hutama-scientific%20report.pdf|url-status=dead}}</ref>thumb|Riemann's explicit formula using the first 200 non-trivial zeros of the zeta function|402x402px
<math display="block">\pi_0(x) = \operatorname{R}(x) - \sum_{\rho}\operatorname{R}(x^\rho),</math>
where
<math display=block>\operatorname{R}(x) = \sum_{n=1}^{\infty} \frac{\mu(n)}{n} \operatorname{li}\left(x^{1/n}\right),</math>
{{math|''μ''(''n'')}} is the [Möbius function](/source/M%C3%B6bius_function), {{math|li(''x'')}} is the [logarithmic integral function](/source/logarithmic_integral_function), {{mvar|ρ}} indexes every zero of the Riemann zeta function, and {{math|li(''x''<sup>{{sfrac|''ρ''|''n''}}</sup>)}} is not evaluated with a [branch cut](/source/branch_cut) but instead considered as {{math|Ei({{sfrac|''ρ''|''n''}} log ''x'')}} where {{math|Ei(''x'')}} is the [exponential integral](/source/exponential_integral). If the trivial zeros are collected and the sum is taken ''only'' over the non-trivial zeros {{mvar|ρ}} of the Riemann zeta function, then {{math|''π''<sub>0</sub>(''x'')}} may be approximated by<ref name="RieselGohl">{{Cite journal | author1-link=Hans Riesel | last1=Riesel | first1=Hans | last2=Göhl | first2=Gunnar | title=Some calculations related to Riemann's prime number formula | doi=10.2307/2004630 | mr=0277489  | year=1970 | journal=[Mathematics of Computation](/source/Mathematics_of_Computation) | issn=0025-5718 | volume=24 | issue=112 | pages=969–983 | jstor=2004630 | publisher=American Mathematical Society |url=https://www.ams.org/journals/mcom/1970-24-112/S0025-5718-1970-0277489-3/S0025-5718-1970-0277489-3.pdf }}</ref>
<math display=block>\pi_0(x) \approx \operatorname{R}(x) - \sum_{\rho}\operatorname{R}\left(x^\rho\right) - \frac{1}{\log x} + \frac{1}{\pi} \arctan{\frac{\pi}{\log x}} .</math>

The [Riemann hypothesis](/source/Riemann_hypothesis) suggests that every such non-trivial zero lies along {{math|1=Re(''s'') = {{sfrac|1|2}}}}.

==Table of {{math|''π''(''x'')}}, {{math|{{sfrac|''x''|log ''x'' }}}}, and {{math|li(''x'')}}==

The table shows how the three functions {{math|''π''(''x'')}}, {{math|{{sfrac|''x''|log ''x''}}}}, and {{math|li(''x'')}} compared at powers of 10. See also,<ref name="Caldwell" /><ref name="Silva">{{cite web |title=Tables of values of {{math|''π''(''x'')}} and of {{math|''π''<sub>2</sub>(''x'')}} |url=https://sweet.ua.pt/tos/primes.html |publisher=Tomás Oliveira e Silva |access-date=2024-03-31}}</ref> and<ref name="Gourdon">{{cite web |title=A table of values of {{math|''π''(''x'')}} |url=http://numbers.computation.free.fr/Constants/Primes/pixtable.html |publisher=Xavier Gourdon, Pascal Sebah, Patrick Demichel |access-date=2008-09-14}}</ref>

:{| class="wikitable" style="text-align: right"
! {{mvar|x}}
! {{math|''π''(''x'')}}
! {{math|''π''(''x'') − {{sfrac|''x''|log ''x''}}}}
! {{math|li(''x'') − ''π''(''x'')}}
! {{math|{{sfrac|''x''|''π''(''x'')}}}}
!{{math|{{sfrac|''x''|log ''x''}}}}<br> % error
|-
| 10
| 4
| 0
| 2
| 2.500
| −8.57%
|-
| 10<sup>2</sup>
| 25
| 3
| 5
| 4.000
| +13.14%
|-
| 10<sup>3</sup>
| 168
| 23
| 10
| 5.952
| +13.83%
|-
| 10<sup>4</sup>
| 1,229
| 143
| 17
| 8.137
| +11.66%
|-
| 10<sup>5</sup>
| 9,592
| 906
| 38
| 10.425
| +9.45%
|-
| 10<sup>6</sup>
| 78,498
| 6,116
| 130
| 12.739
| +7.79%
|-
| 10<sup>7</sup>
| 664,579
| 44,158
| 339
| 15.047
| +6.64%
|-
| 10<sup>8</sup>
| 5,761,455
| 332,774
| 754
| 17.357
| +5.78%
|-
| 10<sup>9</sup>
| 50,847,534
| 2,592,592
| 1,701
| 19.667
| +5.10%
|-
| 10<sup>10</sup>
| 455,052,511
| 20,758,029
| 3,104
| 21.975
| +4.56%
|-
| 10<sup>11</sup>
| 4,118,054,813
| 169,923,159
| 11,588
| 24.283
| +4.13%
|-
| 10<sup>12</sup>
| 37,607,912,018
| 1,416,705,193
| 38,263
| 26.590
| +3.77%
|-
| 10<sup>13</sup>
| 346,065,536,839
| 11,992,858,452
| 108,971
| 28.896
| +3.47%
|-
| 10<sup>14</sup>
| 3,204,941,750,802
| 102,838,308,636
| 314,890
| 31.202
| +3.21%
|-
| 10<sup>15</sup>
| 29,844,570,422,669
| 891,604,962,452
| 1,052,619
| 33.507
| +2.99%
|-
| 10<sup>16</sup>
| 279,238,341,033,925
| 7,804,289,844,393
| 3,214,632
| 35.812
| +2.79%
|-
| 10<sup>17</sup>
| 2,623,557,157,654,233
| 68,883,734,693,928
| 7,956,589
| 38.116
| +2.63%
|-
| 10<sup>18</sup>
| 24,739,954,287,740,860
| 612,483,070,893,536
| 21,949,555
| 40.420
| +2.48%
|-
| 10<sup>19</sup>
| 234,057,667,276,344,607
| 5,481,624,169,369,961
| 99,877,775
| 42.725
| +2.34%
|-
| 10<sup>20</sup>
| 2,220,819,602,560,918,840
| 49,347,193,044,659,702
| 222,744,644
| 45.028
| +2.22%
|-
| 10<sup>21</sup>
| 21,127,269,486,018,731,928
| 446,579,871,578,168,707
| 597,394,254
| 47.332
| +2.11%
|-
| 10<sup>22</sup>
| 201,467,286,689,315,906,290
| 4,060,704,006,019,620,994
| 1,932,355,208
| 49.636
| +2.02%
|-
| 10<sup>23</sup>
| 1,925,320,391,606,803,968,923
| 37,083,513,766,578,631,309
| 7,250,186,216
| 51.939
| +1.93%
|-
| 10<sup>24</sup>
| 18,435,599,767,349,200,867,866
| 339,996,354,713,708,049,069
| 17,146,907,278
| 54.243
| +1.84%
|-
| 10<sup>25</sup>
| 176,846,309,399,143,769,411,680
| 3,128,516,637,843,038,351,228
| 55,160,980,939
| 56.546
| +1.77%
|-
| 10<sup>26</sup>
| 1,699,246,750,872,437,141,327,603
| 28,883,358,936,853,188,823,261
| 155,891,678,121
| 58.850
| +1.70%
|-
| 10<sup>27</sup>
| 16,352,460,426,841,680,446,427,399
| 267,479,615,610,131,274,163,365
| 508,666,658,006
| 61.153
| +1.64%
|-
| 10<sup>28</sup>
| 157,589,269,275,973,410,412,739,598
| 2,484,097,167,669,186,251,622,127
| 1,427,745,660,374
| 63.456
| +1.58%
|-
| 10<sup>29</sup>
| 1,520,698,109,714,272,166,094,258,063
| 23,130,930,737,541,725,917,951,446
| 4,551,193,622,464
| 65.759
| +1.52%
|}
thumb|300px|Graph showing ratio of the prime-counting function {{math|''π''(''x'')}} to two of its approximations, {{math|{{sfrac|''x''|log ''x''}}}} and {{math|Li(''x'')}}. As {{mvar|x}} increases (note {{mvar|x}}-axis is logarithmic), both ratios tend towards 1. The ratio for {{math|{{sfrac|''x''|log ''x''}}}} converges from above very slowly, while the ratio for {{math|Li(''x'')}} converges more quickly from below.
In the [On-Line Encyclopedia of Integer Sequences](/source/On-Line_Encyclopedia_of_Integer_Sequences), the {{math|''π''(''x'')}} column is sequence {{OEIS2C|id=A006880}}, {{math| ''π''(''x'') − {{sfrac|''x''|log ''x''}}}} is sequence {{OEIS2C|id=A057835}}, and {{math|li(''x'') − ''π''(''x'')}} is sequence {{OEIS2C|id=A057752}}.

The value for {{math|''π''(10<sup>24</sup>)}} was originally computed by J. Buethe, [J. Franke](/source/Jens_Franke), A. Jost, and T. Kleinjung assuming the [Riemann hypothesis](/source/Riemann_hypothesis).<ref name="Franke">{{cite web |title=Conditional Calculation of π(10<sup>24</sup>) |first=Jens |last=Franke |author-link=Jens Franke |date=2010-07-29 |url=https://t5k.org/notes/pi(10to24).html |publisher=Chris K. Caldwell |access-date=2024-03-30}}</ref>
It was later verified unconditionally in a computation by D. J. Platt.<ref name="Platt2012">{{cite journal |title=Computing {{math|''π''(''x'')}} Analytically |arxiv=1203.5712 |last1=Platt |first1=David J. |journal=Mathematics of Computation |volume=84 |issue=293 |date=May 2015 |orig-date=March 2012 |pages=1521–1535 |doi=10.1090/S0025-5718-2014-02884-6 |doi-access=free}}</ref>
The value for {{math|''π''(10<sup>25</sup>)}} is by the same four authors.<ref name="Buethe">{{cite web |title=Analytic Computation of the prime-counting Function |url=http://www.math.uni-bonn.de/people/jbuethe/topics/AnalyticPiX.html |publisher=J. Buethe |date=27 May 2014 |access-date=2015-09-01}}  Includes 600,000 value of {{math|''π''(''x'')}} for {{math|10<sup>14</sup> ≤ ''x'' ≤ 1.6×10<sup>18</sup>}}</ref> 
The value for {{math|''π''(10<sup>26</sup>)}} was computed by D. B. Staple.<ref name="Staple">{{cite thesis |title=The combinatorial algorithm for computing π(x) |date=19 August 2015 |url=http://dalspace.library.dal.ca/handle/10222/60524 |publisher=Dalhousie University |access-date=2015-09-01|type=Thesis |last1=Staple |first1=Douglas }}</ref> All other prior entries in this table were also verified as part of that work.

The values for 10<sup>27</sup>, 10<sup>28</sup>, and 10<sup>29</sup> were announced by David Baugh and Kim Walisch in 2015,<ref>{{cite web|website=Mersenne Forum|first=Kim|last=Walisch|title=New confirmed π(10<sup>27</sup>) prime counting function record|date=September 6, 2015|url=http://www.mersenneforum.org/showthread.php?t=20473|access-date=April 25, 2018|archive-date=January 6, 2024|archive-url=https://web.archive.org/web/20240106163603/https://www.mersenneforum.org/showthread.php?t=20473|url-status=dead}}</ref> 2020,<ref>{{cite web |last=Baugh |first=David |date=August 30, 2020 |title=New prime counting function record, pi(10^28) |url=https://www.mersenneforum.org/showpost.php?p=555434&postcount=28 |website=Mersenne Forum |access-date=April 1, 2024 |archive-date=April 1, 2024 |archive-url=https://web.archive.org/web/20240401013804/https://www.mersenneforum.org/showpost.php?p=555434&postcount=28 |url-status=dead }}</ref> and 2022,<ref>{{cite web |first=Kim |last=Walisch |date=March 4, 2022 |title=New prime counting function record: PrimePi(10^29) |url=https://www.mersenneforum.org/showpost.php?p=601061&postcount=38 |website=Mersenne Forum |access-date=April 1, 2024 |archive-date=April 1, 2024 |archive-url=https://web.archive.org/web/20240401013801/https://www.mersenneforum.org/showpost.php?p=601061&postcount=38 |url-status=dead }}</ref> respectively.

== Algorithms for evaluating {{math|''π''(''x'')}} ==

A simple way to find {{math|''π''(''x'')}}, if {{mvar|x}} is not too large, is to use the [sieve of Eratosthenes](/source/sieve_of_Eratosthenes) to produce the primes less than or equal to {{mvar|x}} and then to count them.

A more elaborate way of finding {{math|''π''(''x'')}} is due to [Legendre](/source/Adrien-Marie_Legendre) (using the [inclusion–exclusion principle](/source/inclusion%E2%80%93exclusion_principle)): given {{mvar|x}}, if {{math|''p''<sub>1</sub>, ''p''<sub>2</sub>,…, ''p<sub>n</sub>''}} are distinct prime numbers, then the number of integers less than or equal to {{mvar|x}} which are divisible by no {{mvar|p<sub>i</sub>}} is

:<math>\lfloor x\rfloor - \sum_{i}\left\lfloor\frac{x}{p_i}\right\rfloor + \sum_{i<j} \left\lfloor\frac{x}{p_ip_j}\right\rfloor - \sum_{i<j<k}\left\lfloor\frac{x}{p_ip_jp_k}\right\rfloor + \cdots</math>

(where {{math|⌊''x''⌋}} denotes the [floor function](/source/floor_function)). This number is therefore equal to

:<math>\pi(x)-\pi\left(\sqrt{x}\right)+1</math>

when the numbers {{math|''p''<sub>1</sub>, ''p''<sub>2</sub>,…, ''p<sub>n</sub>''}} are the prime numbers less than or equal to the [square root](/source/square_root) of {{mvar|x}}.

=== The Meissel–Lehmer algorithm ===

{{main|Meissel–Lehmer algorithm}}

In a series of articles published between 1870 and 1885, [Ernst Meissel](/source/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](/source/Natural_number) 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](/source/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](/source/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>

==Other prime-counting functions==

Other prime-counting functions are also used because they are more convenient to work with.

===Riemann's prime-power counting function===
Riemann's prime-power counting function is usually denoted as {{math|Π<sub>0</sub>(''x'')}} or {{math|''J''<sub>0</sub>(''x'')}}. It has jumps of {{math|{{sfrac|1|''n''}}}} at prime powers {{mvar|p<sup>n</sup>}} and it takes a value halfway between the two sides at the discontinuities of {{math|''π''(''x'')}}. That added detail is used because the function may then be defined by an inverse [Mellin transform](/source/Mellin_transform).

Formally, we may define {{math|Π<sub>0</sub>(''x'')}} by
:<math>\Pi_0(x) = \frac{1}{2} \left( \sum_{p^n < x} \frac{1}{n} + \sum_{p^n \le x} \frac{1}{n} \right)\ </math>
where the variable {{mvar|p}} in each sum ranges over all primes within the specified limits.

We may also write
:<math>\ \Pi_0(x) = \sum_{n=2}^x \frac{\Lambda(n)}{\log n} - \frac{\Lambda(x)}{2\log x} = \sum_{n=1}^\infty \frac 1 n \pi_0\left(x^{1/n}\right)</math>
where {{math|Λ}} is the [von Mangoldt function](/source/von_Mangoldt_function) and

:<math>\pi_0(x) = \lim_{\varepsilon \to 0} \frac{\pi(x-\varepsilon) + \pi(x+\varepsilon)}{2}.</math>

The [Möbius inversion formula](/source/M%C3%B6bius_inversion_formula) then gives
:<math>\pi_0(x) = \sum_{n=1}^\infty \frac{\mu(n)}{n}\ \Pi_0\left(x^{1/n}\right),</math>
where {{math|''μ''(''n'')}} is the [Möbius function](/source/M%C3%B6bius_function).

Knowing the relationship between the logarithm of the [Riemann zeta function](/source/Riemann_zeta_function) and the [von Mangoldt function](/source/von_Mangoldt_function) {{math|Λ}}, and using the [Perron formula](/source/Perron_formula) we have
:<math>\log \zeta(s) = s \int_0^\infty \Pi_0(x) x^{-s-1}\, \mathrm{d}x</math>

=== Chebyshev's function ===
The [Chebyshev function](/source/Chebyshev_function) weights primes or prime powers {{mvar|p<sup>n</sup>}} by {{math|log ''p''}}:

:<math>\begin{align}
\vartheta(x) &= \sum_{p\le x} \log p \\
\psi(x)&=\sum_{p^n \le x} \log p = \sum_{n=1}^\infty \vartheta \left( x^{1/n} \right) = \sum_{n \le x}\Lambda(n) .
\end{align}</math>

For {{math|''x'' ≥ 2}},<ref>{{cite book |last=Apostol |first=Tom M. |author-link=Tom M. Apostol |year=2010 |title=Introduction to Analytic Number Theory |publisher=Springer |isbn= 978-1441928054}}</ref>
:<math>\vartheta(x) = \pi(x)\log x - \int_2^x \frac{\pi(t)}{t}\, \mathrm{d}t </math>
and
:<math>\pi(x)=\frac{\vartheta(x)}{\log x} + \int_2^x \frac{\vartheta(t)}{t\log^{2}(t)} \mathrm{d} t .</math>

==Formulas for prime-counting functions==

Formulas for prime-counting functions come in two kinds: arithmetic formulas and analytic formulas. Analytic formulas for prime-counting were the first used to prove the [prime number theorem](/source/prime_number_theorem). They stem from the work of Riemann and [von Mangoldt](/source/Hans_Carl_Friedrich_von_Mangoldt), and are generally known as [explicit formulae](/source/Explicit_formulae_(L-function)).<ref name="Titchmarsh">{{cite book |first=E.C. |last=Titchmarsh |year=1960 |title=The Theory of Functions, 2nd ed. |publisher=Oxford University Press}}</ref>

We have the following expression for the second [Chebyshev function](/source/Chebyshev_function) {{mvar|ψ}}:

:<math>\psi_0(x) = x - \sum_\rho \frac{x^\rho}{\rho} - \log 2\pi - \frac{1}{2} \log\left(1-x^{-2}\right),</math>

where

: <math>\psi_0(x) = \lim_{\varepsilon \to 0} \frac{\psi(x - \varepsilon) + \psi(x + \varepsilon)}{2}.</math>

Here {{mvar|ρ}} are the zeros of the Riemann zeta function in the critical strip, where the real part of {{mvar|ρ}} is between zero and one. The formula is valid for values of {{mvar|x}} greater than one, which is the region of interest. The sum over the roots is [conditionally convergent](/source/Conditional_convergence), and should be taken in order of increasing [absolute value](/source/absolute_value) of the imaginary part. Note that the same sum over the trivial roots gives the last [subtrahend](/source/subtrahend) in the formula.

For {{math|''Π''<sub>0</sub>(''x'')}} we have a more complicated formula

:<math>\Pi_0(x) = \operatorname{li}(x) - \sum_\rho \operatorname{li}\left(x^\rho\right) - \log 2 + \int_x^\infty \frac{\mathrm{d}t}{t \left(t^2 - 1\right) \log t}.</math>

Again, the formula is valid for {{math|''x'' > 1}}, while {{mvar|ρ}} are the nontrivial zeros of the zeta function ordered according to their absolute value.  The first term {{math|li(''x'')}} is the usual [logarithmic integral function](/source/logarithmic_integral_function); the expression {{math|li(''x<sup>ρ</sup>'')}} in the second term should be considered as {{math|Ei(''ρ'' log ''x'')}}, where {{math|Ei}} is the [analytic continuation](/source/analytic_continuation) of the [exponential integral](/source/exponential_integral) function from negative reals to the [complex plane](/source/complex_plane) with branch cut along the positive reals. The final integral is equal to the series over the trivial zeros:

:<math>\int_x^\infty \frac{\mathrm dt}{t \left(t^2 - 1\right) \log t}=\int_x^\infty \frac{1}{t\log t}
\left(\sum_{m}t^{-2m}\right)\,\mathrm dt=\sum_{m}\int_x^\infty \frac{t^{-2m}}{t\log t}
\,\mathrm dt \,\,\overset{\left(u=t^{-2m}\right)}{=}-\sum_{m} \operatorname{li}\left(x^{-2m}\right)
</math>

Thus, [Möbius inversion formula](/source/M%C3%B6bius_inversion_formula) gives us<ref name="RieselGohl" />

:<math>\pi_0(x) = \operatorname{R}(x) - \sum_{\rho}\operatorname{R}\left(x^\rho\right) - \sum_{m} \operatorname{R}\left(x^{-2m}\right)</math>

valid for {{math|''x'' > 1}}, where

:<math>\operatorname{R}(x) = \sum_{n=1}^{\infty} \frac{\mu(n)}{n} \operatorname{li}\left(x^{1/n}\right) = 1 + \sum_{k=1}^\infty \frac{\left(\log x\right)^k}{k! k \zeta(k+1)}</math>

is Riemann's R-function<ref name="mathworld_r">{{MathWorld |title=Riemann Prime Counting Function |urlname=RiemannPrimeCountingFunction}}</ref> and {{math|''μ''(''n'')}} is the [Möbius function](/source/M%C3%B6bius_function). The latter series for it is known as [Gram](/source/J%C3%B8rgen_Pedersen_Gram) series.<ref name="Riesel94">{{cite book | title=Prime Numbers and Computer Methods for Factorization | edition=2nd | first=Hans | last=Riesel | author-link=Hans Riesel | series=Progress in Mathematics | volume=126 | publisher=Birkhäuser | year=1994 | isbn=0-8176-3743-5 | pages=50–51 }}</ref><ref name="mathworld_gram">{{MathWorld |title=Gram Series |urlname=GramSeries}}</ref> Because {{math|log ''x'' < ''x''}} for all {{math|''x'' > 0}}, this series converges for all positive {{mvar|x}} by comparison with the series for {{mvar|e<sup>x</sup>}}. The logarithm in the Gram series of the sum over the non-trivial zero contribution should be evaluated as {{math|''ρ'' log ''x''}} and not {{math|log ''x<sup>ρ</sup>''}}.

Folkmar Bornemann proved,<ref>{{cite web |last=Bornemann | first=Folkmar |title=Solution of a Problem Posed by Jörg Waldvogel |url=http://www-m3.ma.tum.de/bornemann/RiemannRZero.pdf }}</ref> when assuming the [conjecture](/source/conjecture) that all zeros of the Riemann zeta function are simple,<ref group="note">[Montgomery](/source/Hugh_Lowell_Montgomery) showed that (assuming the Riemann hypothesis) at least two thirds of all zeros are simple.</ref> that
:<math>\operatorname{R}\left(e^{-2\pi t}\right)=\frac{1}{\pi}\sum_{k=1}^\infty\frac{(-1)^{k-1}t^{-2k-1}}{(2k+1)\zeta(2k+1)}+\frac12\sum_{\rho}\frac{t^{-\rho}}{\rho\cos\frac{\pi\rho}{2}\zeta'(\rho)}</math>
where {{mvar|ρ}} runs over the non-trivial zeros of the Riemann zeta function and {{math|''t'' > 0}}.

The sum over non-trivial zeta zeros in the formula for {{math|''π''<sub>0</sub>(''x'')}} describes the fluctuations of {{math|''π''<sub>0</sub>(''x'')}} while the remaining terms give the "smooth" part of prime-counting function,<ref name="Watkins">{{cite web |title=The encoding of the prime distribution by the zeta zeros |url=http://www.secamlocal.ex.ac.uk/people/staff/mrwatkin/zeta/encoding1.htm |publisher=Matthew Watkins |access-date=2008-09-14 |archive-date=2013-02-04 |archive-url=https://web.archive.org/web/20130204213356/http://empslocal.ex.ac.uk/people/staff/mrwatkin/zeta/encoding1.htm |url-status=dead }}</ref> so one can use

:<math>\operatorname{R}(x) - \sum_{m=1}^\infty \operatorname{R}\left(x^{-2m}\right)</math>

as a good estimator of {{math|''π''(''x'')}} for {{math|''x'' > 1}}. In fact, since the second term approaches 0 as {{math|''x'' → ∞}}, while the amplitude of the "noisy" part is heuristically about {{math|{{sfrac|{{sqrt|''x''}}|log ''x''}}}}, estimating {{math|''π''(''x'')}} by {{math|R(''x'')}} alone is just as good, and fluctuations of the [distribution of primes](/source/distribution_of_primes) may be clearly represented with the function

:<math>\bigl( \pi_0(x) - \operatorname{R}(x)\bigr) \frac{\log x}{\sqrt x}.</math>

==Inequalities==
[Ramanujan](/source/Srinivasa_Ramanujan)<ref>{{Cite book|url=https://books.google.com/books?id=QoMHCAAAQBAJ|title=Ramanujan's Notebooks, Part IV|last=Berndt|first=Bruce C.|date=2012-12-06|pages=112–113|publisher=Springer Science & Business Media|isbn=9781461269328|language=en}}</ref> proved that the inequality
:<math>\pi(x)^2 < \frac{ex}{\log x} \pi\left( \frac{x}{e} \right)</math>
holds for all sufficiently large values of {{mvar|x}}.

Here are some useful inequalities for {{math|''π''(''x'')}}.

:<math> \frac x {\log x} < \pi(x) < 1.25506 \frac x {\log x} \quad \text{for }x \ge 17.</math>

The left inequality holds for {{math|''x'' ≥ 17}} and the right inequality holds for {{math|''x'' > 1}}. The constant {{#expr:30*ln(113)/113 round 5}} is {{math|30{{sfrac|log 113|113}}}} to 5 decimal places, as {{math|''π''(''x'') {{sfrac|log ''x''|''x''}}}} has its maximum value at {{math|1=''x'' = ''p''<sub>30</sub> = 113}}.<ref name=Rosser1962>{{Cite journal | author-link = J. Barkley Rosser | last1 = Rosser | first1 = J. Barkley | last2 = Schoenfeld | first2 = Lowell | title = Approximate formulas for some functions of prime numbers | journal = [Illinois J. Math.](/source/Illinois_J._Math.) | year = 1962 | volume = 6 | pages = 64–94 | doi = 10.1215/ijm/1255631807 | zbl = 0122.05001 | issn = 0019-2082 | url = https://projecteuclid.org/euclid.ijm/1255631807 | doi-access = free }}</ref>

[Pierre Dusart](/source/Pierre_Dusart) proved in 2010:<ref name = "Dusart2010">{{cite arXiv  |last = Dusart |first = Pierre |author-link = Pierre Dusart |eprint=1002.0442v1 |title = Estimates of Some Functions Over Primes without R.H. |class = math.NT |date = 2 Feb 2010 }}</ref>

:<math> \frac {x} {\log x - 1} < \pi(x) < \frac {x} {\log x - 1.1}\quad \text{for }x \ge 5393 \text{ and }x \ge 60184,\text{ respectively.}</math>

More recently, Dusart has proved<ref>{{cite journal |last = Dusart |first = Pierre |author-link = Pierre Dusart |title = Explicit estimates of some functions over primes |journal = Ramanujan Journal |volume = 45 |issue = 1 |pages=225–234 |date = January 2018 |doi = 10.1007/s11139-016-9839-4|s2cid = 125120533 }}</ref>
(Theorem 5.1) that
:<math>\frac{x}{\log x} \left( 1 + \frac{1}{\log x} + \frac{2}{\log^2 x} \right) \le \pi(x) \le \frac{x}{\log x} \left( 1 + \frac{1}{\log x} + \frac{2}{\log^2 x} + \frac{7.59}{\log^3 x} \right),</math>
for {{math|''x'' ≥ 88789}} and  {{math|''x'' > 1}}, respectively.

Going in the other direction, an approximation for the {{mvar|n}}th  prime, {{mvar|p<sub>n</sub>}}, is
:<math>p_n = n \left(\log n + \log\log n - 1 + \frac {\log\log n - 2}{\log n} + O\left( \frac {(\log\log n)^2} {(\log n)^2}\right)\right).</math>

Here are some inequalities for the {{mvar|n}}th prime. The lower bound is due to Dusart (1999)<ref>{{cite journal
| author-link=Pierre Dusart
| last       = Dusart
| first      = Pierre
| date       = January 1999
| title      = The ''k<sup>th</sup>'' prime is greater than ''k''(ln ''k'' + ln ln ''k'' − 1) for ''k'' ≥ 2
| journal    = Mathematics of Computation
| volume     = 68
| issue      = 225
| pages      = 411–415
| doi        = 10.1090/S0025-5718-99-01037-6
| doi-access = free
| bibcode    = 1999MaCom..68..411D
| url        = https://www.ams.org/mcom/1999-68-225/S0025-5718-99-01037-6/S0025-5718-99-01037-6.pdf
}}</ref> and the upper bound to Rosser (1941).<ref>{{cite journal
| first      = Barkley | last = Rosser | author-link = J. Barkley Rosser
| date       = January 1941
| title      = Explicit bounds for some functions of prime numbers
| jstor      = 2371291
| journal    = American Journal of Mathematics
| volume     = 63
| issue      = 1
| pages      = 211–232
| doi        = 10.2307/2371291
}}</ref>

:<math> n (\log n + \log\log n - 1) < p_n < n (\log n + \log\log n)\quad \text{for } n \ge 6.</math>

The left inequality holds for {{math|''n'' ≥ 2}} and the right inequality holds for {{math|''n'' ≥ 6}}.  A variant form sometimes seen substitutes <math>\log n +\log\log n = \log(n \log n).</math>  An even simpler lower bound is<ref name=Rosser62>{{cite journal
| title      = Approximate formulas for some functions of prime numbers
| first1     = J. Barkley | last1 = Rosser | author1-link = J. Barkley Rosser
| first2     = Lowell | last2 = Schoenfeld | author2-link = Lowell Schoenfeld
| journal    = Illinois Journal of Mathematics
| volume     = 6
| issue      = 1
| pages      = 64–94
| date       = March 1962
| doi        = 10.1215/ijm/1255631807
}}</ref>
:<math>n \log n < p_n,</math>
which holds for all {{math|''n'' ≥ 1}}, but the lower bound above is tighter for {{math|''n'' > ''e<sup>e</sup>'' &asymp;{{#expr:exp(exp(1)) round 3}}}}.

In 2010 Dusart proved<ref name = "Dusart2010" /> (Propositions 6.7 and 6.6) that
:<math> n \left( \log n + \log \log n - 1 + \frac{\log \log n - 2.1}{\log n} \right) \le p_n \le n \left( \log n + \log \log n - 1 + \frac{\log \log n - 2}{\log n} \right),</math>
for {{math|''n'' ≥ 3}} and {{math|''n'' ≥ 688383}}, respectively.

In 2024, Axler<ref>{{cite journal
| title      = New estimates for the ''n''th prime number
| first      = Christian | last = Axler
| journal    = Journal of Integer Sequences
| volume     = 19
| issue      = 4
| article-number = 2
| date       = 2019
| orig-date  = 23 Mar 2017
| arxiv      = 1706.03651
| url        = https://cs.uwaterloo.ca/journals/JIS/VOL22/Axler/axler17.html
}}</ref> further tightened this (equations 1.12 and 1.13) using bounds of the form
:<math> f(n,g(w)) = n \left( \log n + \log\log n - 1 + \frac{\log\log n - 2}{\log n} - \frac{g(\log\log n)}{2\log^2 n} \right)</math>
proving that
:<math> f(n, w^2 - 6w + 11.321) \le p_n \le f(n, w^2 - 6w)</math>
for {{math|''n'' ≥ 2}} and {{math|''n'' ≥ 3468}}, respectively.
The lower bound may also be simplified to {{math|''f''(''n'', ''w''<sup>2</sup>)}} without altering its validity.  The upper bound may be tightened to {{math|''f''(''n'', ''w''<sup>2</sup> − 6''w'' + 10.667)}} if {{math|''n'' ≥ 46254381}}.

There are additional bounds of varying complexity.<ref>{{cite web
| title      = Bounds for ''n''-th prime
| url        = https://math.stackexchange.com/questions/1270814/bounds-for-n-th-prime
| date       = 31 December 2015
| website    = Mathematics StackExchange
}}</ref><ref>{{cite journal
| title      = New Estimates for Some Functions Defined Over Primes 
| first      = Christian | last = Axler
| journal    = Integers
| volume     = 18
| article-number = A52
| doi        = 10.5281/zenodo.10677755
| doi-access = free
| date       = 2018
| orig-date  = 23 Mar 2017
| arxiv      = 1703.08032
| url        = https://math.colgate.edu/~integers/s52/s52.pdf
}}</ref><ref>{{cite journal
| title      = Effective Estimates for Some Functions Defined over Primes 
| first      = Christian | last = Axler
| journal    = Integers
| volume     = 24
| article-number = A34
| doi        = 10.5281/zenodo.10677755
| doi-access = free
| date       = 2024
| orig-date  = 11 Mar 2022
| arxiv      = 2203.05917 
| url        = https://math.colgate.edu/~integers/y34/y34.pdf
}}</ref>

==The Riemann hypothesis==

The [Riemann hypothesis](/source/Riemann_hypothesis) implies a much tighter bound on the error in the estimate for {{math|''π''(''x'')}}, and hence to a more regular distribution of prime numbers,

:<math>\pi(x) = \operatorname{li}(x) + O(\sqrt{x} \log{x}).</math>
Specifically,<ref>{{Cite journal | last1=Schoenfeld | first1=Lowell |author-link=Lowell Schoenfeld| title=Sharper bounds for the Chebyshev functions ''θ''(''x'') and ''ψ''(''x''). II | doi=10.2307/2005976 | mr=0457374  | year=1976 | journal=[Mathematics of Computation](/source/Mathematics_of_Computation) | issn=0025-5718 | volume=30 | issue=134 | pages=337–360 | jstor=2005976 | publisher=American Mathematical Society}}</ref>

:<math>|\pi(x) - \operatorname{li}(x)| < \frac{\sqrt{x}}{8\pi} \, \log{x}, \quad \text{for all } x \ge 2657. </math>

{{harvtxt|Dudek|2015}} proved that the Riemann hypothesis implies that for all {{math|''x'' ≥ 2}} there is a prime {{mvar|p}} satisfying
:<math>x - \frac{4}{\pi} \sqrt{x} \log x < p \leq x.</math>

== See also ==
* [Bertrand's postulate](/source/Bertrand's_postulate)
* [Oppermann's conjecture](/source/Oppermann's_conjecture)
* [Ramanujan prime](/source/Ramanujan_prime)

==References==
{{Reflist}}
===Notes===
{{reflist|group=note}}
==External links==
*Chris Caldwell, [http://primes.utm.edu/nthprime/ ''The Nth Prime Page''] at The [Prime Pages](/source/Prime_Pages).
*Tomás Oliveira e Silva, [http://sweet.ua.pt/tos/primes.html Tables of prime-counting functions].
* {{Citation| last=Dudek|first=Adrian W.|date=2015|title=On the Riemann hypothesis and the difference between primes|journal=International Journal of Number Theory|volume=11|issue=3|pages=771–778|doi=10.1142/S1793042115500426|issn=1793-0421|arxiv=1402.6417|bibcode=2014arXiv1402.6417D|s2cid=119321107}}

{{DEFAULTSORT:Prime-Counting Function}}
Category:Analytic number theory
Category:Prime numbers
Category:Arithmetic functions

---
Adapted from the Wikipedia article [Prime-counting function](https://en.wikipedia.org/wiki/Prime-counting_function) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Prime-counting_function?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.