Prime Number Theorem

$\pi(n) = $ the number of prime numbers $\leq n$. The Prime Number Theorem states that $\pi(n) \approx \frac{n}{\ln(n)}$. In the following we consider all primes $\leq 1.000.000$. First we computer a bitvector 'prime' such that prime[p] is true if and only p is a prime number.

In [1]:
prime = [True] * 1000001
for p in range(2, 1000001):
    for f in range(2 * p, 1000001, p):
        prime[f] = False

We next compute select all the prime numbers in the range 2..100, i.e. idx where prime[idx] = True.

In [2]:
primes = [p for p in range(2, 1000001) if prime[p]]
In [3]:
primes[:10]
Out[3]:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
In [4]:
import matplotlib.pyplot as plt
import math
In [5]:
X = range(2, 1000001, 25000)
Y = [len([p for p in primes if p<=x]) for x in X] # slow
plt.plot(X, Y, '.g')
plt.plot(X,[x / math.log(x) for x,y in zip(X, Y)], 'r-')
plt.show()