There are no approved revisions of this page, so it may
not have been
reviewed.
As an
arithmetic function defined over the
positive integers, the
prime counting function counts how many
primes there are up to
.
for
.
For example,
since the set of primes up to
is
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97} 
.
A000720 , the number of primes
. (Sometimes called
to distinguish it from the number
)

{0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 17, 17, ...} 
The sequence gives
for
integer values of
starting with
. Note that although the value of the
stepwise function is always an integer, its argument may be any real number,
rational or
irrational. Thus,
and
.
^{[1]}
Algorithms
There are several efficient algorithms for computing the value of
which fall into the two categories of
The value is available in PARI/GP as "primepi(x)" and "PrimePi[x] in Mathematica.
Dirichlet generating function
The Dirichlet generating function for the prime counting function is
 $D_{\{\pi (n)\}}(s):=\sum _{n=1}^{\infty }{\frac {\pi (n)}{n^{s}}}=\sum _{i=1}^{\infty }{\frac {s^{p_{i}}}{1s}}={\frac {b(s)}{1s}},\,$
where
is the
th prime and
is the Dirichlet generating function for the
characteristic function of prime numbers (
A010051).
Asymptotic behavior
The
prime number theorem gives us a means to obtain an estimate which becomes more accurate (in terms of relative error) the larger
is
 $\pi (x)\sim {\frac {x}{\log x}},\,$^{[2]}
since
 $\lim _{x\to \infty }{\frac {\pi (x)\log x}{x}}=1.\,$^{[3]}
In
Wilson's prime recurrence (see
A007097), we have
, since
is the
th prime.
We could consider the prime counting function to be the specific case
of the function
which tallies how many numbers up to
have
prime factors. From the prime number theorem we can derive the following approximation (when
, the whole second multiplicand becomes just
)
 $\pi _{k}(x)\sim {\frac {x}{\log x}}{\frac {(\log \log x)^{k1}}{(k1)!}}.\,$
Alternate definitions
The primecounting function is the summatory function of the characteristic function of prime numbers
 $\pi (n):=\sum _{i=1}^{n}\chi _{\{{\mbox{prime}}\}}(i)=\sum _{i=1}^{n}[\gcd(i,\lfloor {\sqrt {i}}\rfloor \#)=1],\,$
where
is the
primorial of
and
is the
Iverson bracket.
As an arithmetic function defined over the real numbers, we get
 $\pi (x)=\sum _{i=1}^{\lfloor x\rfloor }\chi _{\{{\mbox{prime}}\}}(i).\,$
We could also define it as
 $\pi (x)=\sum _{i=1}^{\lfloor x\rfloor }[\sigma _{0}(i)=i^{0}+1]=\sum _{i=1}^{\lfloor x\rfloor }[\sigma _{0}(i)=2],\,$
where
is the
Iverson bracket, or as
 $\pi (x)=\sum _{i=1}^{\lfloor x\rfloor }[\sigma _{1}(i)=i^{1}+1]=\sum _{i=1}^{\lfloor x\rfloor }[\sigma _{1}(i)=i+1],\,$
or (is the following true?)
 $(?)\ \pi (x)=\sum _{i=1}^{\lfloor x\rfloor }[\sigma _{k}(i)=i^{k}+1],\,$
with
(
,
tau(n)) being the
number of divisors function,
(
,
sigma(n)) being the
sum of divisors function and
(
divisor function) being the
sum of kth powers of divisors function.
Number of primes less than b^n
The number of primes less than or equal to
gives the number of divisions required to determine the
primality of
by
trial division.
Number of primes less than or equal to 2^n
A007053 Number of primes
.

{0, 1, 2, 4, 6, 11, 18, 31, 54, 97, 172, 309, 564, 1028, 1900, 3512, 6542, 12251, 23000, 43390, 82025, 155611, 295947, 564163, 1077871, 2063689, 3957809, 7603553, 14630843, 28192750, 54400028, ...} 
Number of primes less than or equal to 2^(2^n)
A153450 Number of primes
.

{1, 2, 6, 54, 6542, 203280221, ...} 
The primes up to
are exactly determined from the primes up to
with the
sieve of Eratosthenes. This gives an inductive algorithm to find all primes up to any integer (modulo space and time constraints...) This means that all odd primes are ultimately determined by the only even prime, namely 2, the oddest prime...
The primes less than or equal to
where each subset is exactly determined by the preceding subset, are

{{2}, {2, 3}, {2, 3, 5, 7, 11, 13}, {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251}, ...} 
Number of primes less than e^n
A040014 Number of primes
.

{0, 1, 4, 8, 16, 34, 79, 183, 429, 1019, 2466, 6048, 14912, 37128, 93117, 234855, 595341, 1516233, 3877186, 9950346, 25614562, 66124777, 171141897, 443963543, 1154106844, 3005936865, ...} 
Number of primes less than 10^n
A006880 Number of primes
.

{0, 4, 25, 168, 1229, 9592, 78498, 664579, 5761455, 50847534, 455052511, 4118054813, 37607912018, 346065536839, 3204941750802, 29844570422669, 279238341033925, 2623557157654233, ...} 
See also
Notes
 ↑ being the prime counting function while is the constant pi, being the Golden ratio.
 ↑ In number theory, the function always refers to the natural logarithm, i.e. the logarithm to the base , , being Euler's number. The reason this needs to be clarified here is that in the slew of books on the Riemann hypothesis that came out before Dan Rockmore's Stalking the Riemann Hypothesis, you will more likely see this formula stated with "ln" rather than "log".
 ↑ Manfred R. Schroeder, Number Theory in Science and Communication: With Applications in Cryptography, Physics, Digital Information, Computing and SelfSimilarity, 5th Ed. Springer (2009) p. 50.