Prime Number Theorem

The Prime Number Theorem (PNT) describes the asymptotic distribution of prime numbers. It answers "how dense" the primes are.

The Prime Counting Function

Let

π (x)

be the number of primes less than or equal to

x

Theorem (Prime Number Theorem)

x \to \infty

π (x) \sim \frac{x}{ln x}

Meaning:

x \to \infty lim \frac{π ( x )}{x / ln x} = 1

A better approximation is given by the logarithmic integral function:

π (x) \approx Li (x) = \int_{2}^{x} \frac{d t}{ln t}

Probability: The probability that a random integer $n$ is prime is roughly $1/ ln n$ .
n-th Prime: The $n$ -th prime number $p_{n}$ is approximately $n ln n$ .

A related, concrete bound: For every integer

n > 1

, there is always a prime

p

such that:

n < p < 2 n

Exercise (Problem 1)

Estimate the number of primes less than 1,000,000 using PNT.

Exercise (Problem 2)

Use Bertrand's Postulate to prove that

n!

is not a perfect power for

n > 1

Exercise (Problem 3)

Prove that

lim_{n \to \infty} \frac{p _{n + 1}}{p _{n}} = 1