This site is supported by donations to The OEIS Foundation.

# Prime counting function

As an arithmetic function defined over the positive integers, the prime counting function
 π (x)
counts how many primes there are up to
 x
.
 π (x) = 0
for
 x < 2
.
For example,
 π (100) = 25
since the set of primes up to
 100
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
 pi (n)
, the number of primes
 ≤   n
. (Sometimes called
 PrimePi (n)
to distinguish it from the number
 3.14159...
)
 {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
 π (x)
for integer values of
 x
starting with
 x = 1
. Note that although the value of the stepwise function is always an integer, its argument may be any real number, rational or irrational. Thus,
π(
 22 7
) = 2, π (π) = 2
and
 π (e) = 1
.[1]

## Algorithms

There are several efficient algorithms for computing the value of
 π (x)
which fall into the two categories of
• combinatorial algorithms (which calculate the number of primes by inclusion-exclusion),
• analytic algorithms (which calculate the Riemann zeta function ζ (x)
or other functions to high precision).

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

${\displaystyle D_{\{\pi (n)\}}(s):=\sum _{n=1}^{\infty }{\frac {\pi (n)}{n^{s}}}=\sum _{i=1}^{\infty }{\frac {s^{p_{i}}}{1-s}}={\frac {b(s)}{1-s}},\,}$
where
 pi
is the
 i
th prime and
 b (s)
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
 x
is
${\displaystyle \pi (x)\sim {\frac {x}{\log x}},\,}$[2]

since

${\displaystyle \lim _{x\to \infty }{\frac {\pi (x)\log x}{x}}=1.\,}$[3]
In Wilson's prime recurrence
 Wn
(see A007097), we have
 π (Wn) = Wn   − 1
, since
 Wn
is the
 Wn   − 1
th prime. We could consider the prime counting function to be the specific case
 π1(x)
of the function
 πk (x)
which tallies how many numbers up to
 x
have
 k
prime factors. From the prime number theorem we can derive the following approximation (when
 k = 1
, the whole second multiplicand becomes just
 1
)
${\displaystyle \pi _{k}(x)\sim {\frac {x}{\log x}}{\frac {(\log \log x)^{k-1}}{(k-1)!}}.\,}$

## Alternate definitions

The prime-counting function is the summatory function of the characteristic function of prime numbers

${\displaystyle \pi (n):=\sum _{i=1}^{n}\chi _{\{{\mbox{prime}}\}}(i)=\sum _{i=1}^{n}[\gcd(i,\lfloor {\sqrt {i}}\rfloor \#)=1],\,}$
where
 n#
is the primorial of
 n
and
 [·]
is the Iverson bracket.

As an arithmetic function defined over the real numbers, we get

${\displaystyle \pi (x)=\sum _{i=1}^{\lfloor x\rfloor }\chi _{\{{\mbox{prime}}\}}(i).\,}$

We could also define it as

${\displaystyle \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
${\displaystyle \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?)

${\displaystyle (?)\ \pi (x)=\sum _{i=1}^{\lfloor x\rfloor }[\sigma _{k}(i)=i^{k}+1],\,}$
with
 σ0(n)
(
 τ (n)
, tau(n)) being the number of divisors function,
 σ1(n)
(
 σ (n)
, sigma(n)) being the sum of divisors function and
 σk (n)
(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
 b n
gives the number of divisions required to determine the primality of
 b 2n
by trial division.

### Number of primes less than or equal to 2^n

A007053 Number of primes
 ≤   2 n, n   ≥   0
.
 {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
 ≤   2 2 n = PiPrime(A001146), n   ≥   0
.
 {1, 2, 6, 54, 6542, 203280221, ...}
The primes up to
 2 2 n
are exactly determined from the primes up to
 2 2 n   − 1, n   ≥   1,
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
 2 2 n, n   ≥   0,
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
 < e n, n   ≥   0
.
 {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
 < 10 n, n   ≥   0
.
 {0, 4, 25, 168, 1229, 9592, 78498, 664579, 5761455, 50847534, 455052511, 4118054813, 37607912018, 346065536839, 3204941750802, 29844570422669, 279238341033925, 2623557157654233, ...}

## Notes

1.  π (x)
being the prime counting function while
 π
is the constant pi,
 ϕ
being the Golden ratio.
2. In number theory, the function
 log x
always refers to the natural logarithm, i.e. the logarithm to the base
 e
,
 loge x
,
 e
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".
3. Manfred R. Schroeder, Number Theory in Science and Communication: With Applications in Cryptography, Physics, Digital Information, Computing and Self-Similarity, 5th Ed. Springer (2009) p. 50.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 9, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}