Prime Number Theorem

In number theory, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs. - Wiki

The definition above is hard to understand. To put it simply, PNT provides us with an estimation for Prime-Counting Function.

What is Prime-Counting Function?

This brings out another Wiki definition:

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 denoted by $\pi (x)$ (this does not refer to the number $\pi$). - Wiki

This definition is easy to understand. Prime-Counting Function, $\pi (N)$, gives us number of primes less than or equal to $N$. For example, $\pi (10) = 4$ since there are $4$ primes, $\{ 2 , 3 , 5 , 7 \}$, which are $\leq 10$.

PNT - Estimation for $\pi (N)$

So, as I was saying before, PNT provides us with an estimation for Prime-Counting Function. It states that:

$$ \pi (N) \approx \frac {N}{ln(N)}$$
The accuracy of the estimation increase as $N$ becomes larger.

Application

We can use the theorem for complexity analysis.

Reference

Labels: Number Theory, Prime