The prime counting function is the function 
giving the
number of primes less than or equal to a given number
(Shanks 1993, p. 15). For example,
there are no primes 
, so 
. There is a single prime (2) 
, so 
. There are two primes (2 and 3) 
, so 
. And so on.
The notation 
for the prime counting function
is slightly unfortunate because it has nothing whatsoever to do with the constant
. This notation was introduced
by number theorist Edmund Landau in 1909 and has now become standard. In the words
of Derbyshire (2004, p. 38), "I am sorry about this; it is not my fault.
You'll just have to put up with it."
Letting 
denote the 
th prime,
is a right
inverse of 
since
 |
(1)
|
for all positive integers. Also,
 |
(2)
|
iff 
is a prime
number.
The first few values of 
for 
, 2, ... are
0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, ... (OEIS A000720).
The Wolfram Language command giving
the prime counting function for a number 
is PrimePi[x],
which works up to a maximum value of 
.
The notation 
is used to denote the modular
prime counting function, i.e., the number of primes of the form 
less than or
equal to 
(Shanks 1993, pp. 21-22).
The following table gives the values of 
for powers
of 10 (OEIS A006880), extending other printed
tabulations (e.g., Hardy and Wright 1979, p. 4; Shanks 1993, pp. 242-243;
Ribenboim 1996, p. 237; Derbyshire 2004, p. 35). Note that 
was incorrectly
computed as 
by Meissel (1885), which is off
by 56 (Havil 2003, p. 171), a result quoted by Hardy and Wright (1979) and Hardy
(1999) and sometimes (erroneously) known as Bertelsen's
number. The value for 
comes
from Deleglise and Rivat (1996), and 
was
reported by X. Gourdon on Oct. 27, 2000. Oliveira e Silva and X. Gourdon
independently computed values for 
and
, but an error was found in
the computations of Gourdon. The value given for 
was
computed by Tomás Oliveira e Silva, who verified this result using set sets
of hardware and program parameters (pers. comm., Apr. 7, 2008). (Values of 
computed independently by Oliveira
e Silva and X. Gourdon already agree for all powers of 10 up to 
.) 
was
computed by Büthe (2014), 
by Staple
in 2014 (Staple 2015), and 
by D. Baugh
and K. Walisch (2015) using the primecount fast prime counting function
implementation (Walisch).
 |  | reference |
| 1 | 4 | antiquity |
| 2 |  | L. Pisano (1202; Beiler) |
| 3 |  | F. van Schooten (1657; Beiler) |
| 4 |  | F. van Schooten (1657; Beiler) |
| 5 |  | T. Brancker (1668; Beiler) |
| 6 |  | A. Felkel (1785; Beiler) |
| 7 |  | J. P. Kulik (1867; Beiler) |
| 8 |  | Meissel (1871; corrected) |
| 9 |  | Meissel (1886; corrected) |
| 10 |  | Lehmer (1959; corrected) |
| 11 |  | Bohmann (1972; corrected) |
| 12 |  | |
| 13 |  | |
| 14 |  | Lagarias et al. (1985) |
| 15 |  | Lagarias et al. (1985) |
| 16 |  | Lagarias et al. (1985) |
| 17 |  | M. Deleglise and J. Rivat (1994) |
| 18 |  | Deleglise and Rivat (1996) |
| 19 |  | M. Deleglise (June 19, 1996) |
| 20 |  | M. Deleglise (June 19, 1996) |
| 21 |  |  project (Dec. 2000) |
| 22 |  | P. Demichel and X. Gourdon (Feb. 2001) |
| 23 |  | T. Oliveira e Silva (pers. comm., Apr. 7, 2008) |
| 24 |  | Platt |
| 25 |  | Büthe (2014) |
| 26 |  | Staple (2015) |
| 27 |  | D. Baugh and K. Walisch (2015) |
One of the most fundamental and important results in number theory is the asymptotic form of 
as 
becomes large.
This is given by the prime number theorem,
which states that
 |
(3)
|
where 
is the logarithmic
integral and 
is asymptotic
notation. This relation was first postulated by Gauss in 1792 (when he was 15
years old), although not revealed until an 1849 letter to Johann Encke and not published
until 1863 (Gauss 1863; Havil 2003, pp. 176-177).
The following table compares the prime counting function 
, Riemann
prime counting function 
, and logarithmic
integral 
for powers of ten, i.e., 
. The corresponding
differences are plotted above for small 
. Note that the
values given by Hardy (1999, p. 26) for 
are incorrect.
In the following table, ![[x]](/images/equations/PrimeCountingFunction/Inline75.svg)
denotes the
nearest integer function. A similar table
comparing 
and 
is given
by Borwein and Bailey (2003, p. 65).
![[pi(10^n)-R(10^n)]](/images/equations/PrimeCountingFunction/Inline79.svg)
![[pi(10^n)-Li(10^n)]](/images/equations/PrimeCountingFunction/Inline80.svg)
The prime counting function can be expressed by Legendre's formula, Lehmer's formula, Mapes'
method, or Meissel's formula. A brief history
of attempts to calculate 
is given by
Berndt (1994). The following table is taken from Riesel (1994), where 
is asymptotic
notation.
| method | time complexity | storage complexity |
| Lagarias-Miller-Odlyzko |  |  |
| Lagarias-Odlyzko 1 |  |  |
| Lagarias-Odlyzko 2 |  |  |
| Legendre's formula |  |  |
| Lehmer |  |  |
| Mapes' method |  |  |
| Meissel |  |  |
An approximate formula due to Locker-Ernst (Locker-Ernst 1959; Panaitopol 1999; Havil 2003, pp. 179-180), illustrated above, is given by
 |
(4)
|
where 
is related to the harmonic
number 
by 
. This
formula is within 
of the
actual value for 
.
The values for which 
are 1, 109, 113, 114, 199, 200, 201, ... (OEIS A051046).
Panaitopol (1999) shows that this quantity is positive for all 
.
An upper bound for 
is given by
 |
(5)
|
for 
, and a lower bound by
 |
(6)
|
for 
(Rosser and Schoenfeld 1962).
Hardy and Wright (1979, p. 414) give the formula
![pi(n)=-1+sum_(j=3)^n[(j-2)!-j|_((j-2)!)/j_|]](/images/equations/PrimeCountingFunction/NumberedEquation7.svg) |
(7)
|
for 
, where 
is the floor function.
A modified version of the prime counting function is given by
 |
(8)
|
 |
(9)
|
where 
is the Möbius
function and 
is the Riemann
prime counting function.
Ramanujan also showed that
 |
(10)
|
where 
is the Möbius
function (Berndt 1994, p. 117; Havil 2003, p. 199).
The smallest 
such that 
for
, 3, ... are 2, 27, 96, 330, 1008,
... (OEIS A038625), and the corresponding 
are 1, 9, 24, 66, 168, 437, ...
(OEIS A038626). The number of solutions of
for 
, 3, ... are
4, 3, 3, 6, 7, 6, ... (OEIS A038627).
Ramanujan showed that for sufficiently large 
,
 |
(11)
|
This holds for 
, 9, 10, 12, 14, 15, 16, 18, ... (OEIS
A091886). The largest known prime
for which the inequality fails is 
(Berndt
1994, pp. 112-113). The related inequality
![[li(x)]^2<(ex)/(lnx)li(x/e)](/images/equations/PrimeCountingFunction/NumberedEquation12.svg) |
(12)
|
where
 |
(13)
|
is true for 
and no smaller number (Berndt
1994, p. 114).
II." 26 Oct 2014. 
: The Meissel,
Lehmer, Lagarias, Miller, Odlyzko Method." Math. Comput. 65, 235-245,
1996.Derbyshire, J. 
-tuplets."
: The Meissel-Lehmer Method."
Math. Comput. 44, 537-560, 1985.Lagarias, J. and Odlyzko,
A. "Computing 
: An Analytic
Method." J. Algorithms 8, 173-191, 1987.Locker-Ernst,
L. "Bemerkung über die Verteilung der Primzahlen." Elemente Math.
(Basel) 14, 1-5, 1959.Mapes, D. C. "Fast Method
for Computing the Number of Primes Less than a Given Limit." Math. Comput. 17,
179-185, 1963.Meissel, E. D. F. "Über die Bestimmung
der Primzahlmenge innerhalb gegebener Grenzen." Math. Ann. 2,
636-642, 1870.Meissel, E. D. F. "Berechnung der Menge
von Primzahlen, welche innerhalb der ersten Milliarde naturlicher Zahlen vorkommen."
Math. Ann. 25, 251-257, 1885.Nagell, T. "The Function
." §16 in 
." Math.
Ineq. Appl. 2, 317-324, 1999.Platt, D. "Computing 
Analytically." To appear in
Math. Comput.Ribenboim, P. 
." 
)." §8.7
in 
."