Prime counting function

The 60 first values of π(n)

In mathematics, the prime counting function is the function counting the number of prime numbers less than or equal to some real number x. It is written as $\pi (x)$, but it is not related to the number π. Some key values of the function include $\pi (1)=0$, $\pi (2)=1$ and $\pi (3)=2$.

In general, if $p_{n}$stands for the n-th prime number, then $\pi (p_{n})=n$.

History

Of great interest in number theory is the growth rate of the prime-counting function. It was conjectured in the end of the 18th century by Gauss and by Legendre to be approximately

${\frac {x}{\log(x)}}$

where log is the natural logarithm, in the sense that

$\lim _{x\rightarrow \infty }{\frac {\pi (x)}{x/\log(x)}}=1.$

This statement is the prime number theorem. An equivalent statement is

$\lim _{x\rightarrow \infty }\pi (x)/\operatorname {li} (x)=1$

where li is the logarithmic integral function. The prime number theorem was first proved in 1896 by Jacques Hadamard and by Charles de la Vallée Poussin independently, using properties of the Riemann zeta function introduced by Riemann in 1859. Proofs of the prime number theorem not using the zeta function or complex analysis were found around 1948 by Atle Selberg and by Paul Erdős (for the most part independently).

Algorithms for evaluating π(x)

A simple way to find $\pi (x)$, if $x$ is not too large, is to use the sieve of Eratosthenes to produce the primes less than or equal to $x$ and then to count them.

A more elaborate way of finding $\pi (x)$ is due to Legendre (using the inclusion–exclusion principle): given $x$, if $p_{1},p_{2},\ldots ,p_{n}$ are distinct prime numbers, then the number of integers less than or equal to $x$ which are divisible by no $p_{i}$ is

$\lfloor x\rfloor -\sum _{i}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor +\sum _{i<j}\left\lfloor {\frac {x}{p_{i}p_{j}}}\right\rfloor -\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_{j}p_{k}}}\right\rfloor +\cdots$

(where $\lfloor {x}\rfloor$ denotes the floor function). This number is therefore equal to

$\pi (x)-\pi \left({\sqrt {x}}\right)+1$

when the numbers $p_{1},p_{2},\ldots ,p_{n}$ are the prime numbers less than or equal to the square root of $x$.

Related pages

• Ramanujan prime