What is the ratio of prime numbers to all numbers ?
Prime numbers are one of the most fascinating topics in mathematics. Although many mathematicians have tried to formulate prime numbers, it has turned out that they don't appear to follow any specific pattern. Prime numbers are widely used in cryptography, especially in asymmetric key cryptography algorithms such as RSA.
In my early days in college, when I was a beginner programmer, I wrote a C++ program to factor prime numbers. I wanted to find out what the largest prime number I could factor was. Since I wasn't using the most efficient algorithm, the program was very slow, and it became even slower as it reached larger numbers.I'm quite sure that many of you have done this exercise at about the same point in your programming journey.
Yesterday, after midnight, I thought that prime numbers are actually very rare, and the ratio of prime numbers to all numbers approaches zero as you consider a larger interval of integers. I grabbed my laptop and wrote this simple Go code. It appears that prime numbers are indeed very rare, although they always exist.
package main
import "fmt"
func sieveOfEratosthenes(max int) []int {
sieve := make([]bool, max+1)
for i := range sieve {
sieve[i] = true
}
sieve[0], sieve[1] = false, false
for p := 2; p*p <= max; p++ {
if sieve[p] {
for i := p * p; i <= max; i += p {
sieve[i] = false
}
}
}
primes := []int{}
for i := 2; i <= max; i++ {
if sieve[i] {
primes = append(primes, i)
}
}
return primes
}
func main() {
max := 100000000
primeNumbers := sieveOfEratosthenes(max)
ratio := float64(len(primeNumbers)) / float64(max)
fmt.Printf("%.6f\n", ratio)
}
Sieve of Eratosthenes is an ancient algorithm to find all prime numbers up to a given maximum number, its of course much faster than I used to do in the past 🤣.
The prime number ratio decreases as the upper bound is increased, as seen in the above chart. The fact that the rate of decline progressively slows down is interesting. This implies that prime numbers will probably continue forever and never completely vanish, even though the ratio decreases with each increase in the upper bound.
After conducting some online research, I found out that this phenomenon is a property of prime numbers, as stated by the Prime Number Theorem. There's actually a solid mathematical proof for this behavior.
The key takeaway from this is that you should never discourage yourself from thinking before going to bed. It just might lead to fascinating mathematical insights! 🤣🤣🤣.
