A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers.

Euclid proved the infinity of primes by contradiction.

Assume there are a finite number, n , of primes , the largest being \(p_n\);

Consider the number that is the product of these, plus one: \(N = \prod\limits_{i = 1}^n {{p_i}} + 1\)

By construction, \(N\) is not divisible by any of the \(p_i\).

Hence it is either prime itself, or divisible by another prime greater than \(p_n\), contradicting the assumption.

Euclid’s proof is the easiest to understand, especially if you’re not well-versed in mathematics, but now I am going to introduce another proof of the infinitude of primes, which is shorter and I also find it to be the most appealing, at least in my eyes.

In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number \(x\). E.g. for \(x=10.124\), we have that 4 number of prime number: 2, 3, 5, 7.

In other words, we can say that \(\pi(x)\) “behaves” like \(x/\ln (x)\) when \(x\) is approaching infinity — there’s an asymptotic ‘equality’.

So, there are infinite primes.

For Python code, we use SymPy – a Python library for symbolic mathematics. In particular, we’ll use primerange(a, b) for generate all prime numbers in the range [a, b).

This entry was posted on lunedì, Settembre 13th, 2021 at 19:03 and is filed under math, python. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.