Just how many Prime Numbers are there? A simple pythonic approach

Mathematics seems to be fascinated by prime numbers and the number of prime numbers in particular. Prime numbers are said to be discovered by ancient greeks at around 300BC. Interestingly, one of the best methods for finding prime numbers was discovered by Greek known as Eratosthenes. Gauss, Legendre, and a myriad of other mathematicians later expanded these works.

A prime number theorem provides a way to approximate the number of primes less than or equal to a given number n. This value is called π(n), where π is the “prime counting function.” For example, π(10) = 4, since four primes are less than or equal to 10 (2, 3, 5, and 7). Similarly, π(100) = 25, since 25 of the first 100 integers are prime. Among the first 1,000 integers, there are 168 primes, so π(1,000) = 168, and so on. Note that as we considered the first 10, 100, and 1,000 integers, the percentage of primes went from 40% to 25% to 16.8%. These examples suggest, and the prime number theorem confirms, that the density of prime numbers at or below a given number decreases as the number gets larger.

But is there a way of determining all primes numbers up to a, let’s say a trillion. The prime number theorem offers an approximation to solve this computationally vast problem.
Basically, as per theorem π(n) or the number of primes occurring, n is equal to n * ln(n), where ln is the natural logarithm. This is because the ratio of π(n) to n/ ln(n) approaches what is known as an asymptotic value near infinity, which means at large values of n, it becomes constant. This seems counter-intuitive as the gaps between prime numbers increase almost exponentially, but we will see later on that even with a simple function, this relationship seems true.

We will use simple python functions and computations to find work on the Prime Number Theorem instead of using complicated mathematics.
Let’s start with the most basic algorithm for generating Prime numbers, the legendary “Sieve of Eratosthenes.”

The algorithm’s gist goes that we create a list of prime number candidates till the maximum number specified. Using repeated filters or sieves, which are essentially the first few prime numbers, i.e., 2,3,5, we remove the divisible numbers by these first few primes. So, essentially the sieve is the divisibility test of a number with a known prime.

Let's start with build a basic sieve function.

The above code, although workable, is a little slow. Let replace some parts using the NumPy library

Let's write a timer function to check out function execution timelines

The sieve-based or deterministic method however fails to generate truly large prime numbers required for computing purposes. For RSA prime number generation we require probability methods such as the Miller-Rabin test with some acceptable level of error such as 1/2e128. These tests will essentially give you a probability that the number is prime instead of finding the exact prime for a given N.

We can use the python Crypto library to generate prime of N bits, but since it uses probabilistic methods it is not suitable for our analysis.

Let's build a simple computation loop for checking the hypothesis of the theorem as discussed above.

The approximation much closely for the first 25000 natural numbers

We can see from the first experiments that the ratio of prime numbers to natural numbers falls drastically as N increases, so each corresponding interval will produce fewer prime numbers. Let check this by creating a prime gap function

So in the above figure, the x-axis is 2 N bit based and the y-axis is the log of difference between two primes

What about the error of π(n) and its approximate function

The error shows a near straight line on log scale

So how many prime numbers are there?

N / Ln(N) seems to be a good approximation as shown above. Hence for the 1 trillion intervals, there must be at least 3.6% of primes. For the 1e20 interval, there must be at least around 2.2% prime numbers in the interval.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store