$\begingroup$

Wikipedia says that the largest known prime number is $2^{43,112,609}-1$ and it has 12,978,189 digits. I keep running into this question/answer over and over, but I haven't been able to find how many known prime numbers exist. The website primes.utm.edu allows downloading of the first 50,000,000 known primes so I know there are at least that many; I'm not expecting to find a list of all known primes, but is there any information on how many there are known?

edit Relevant video from Khan Academy: Prime Number Theorem: the density of primes

$\endgroup$ 14

4 Answers

$\begingroup$

Nobody's really keeping count.

Newly discovered large primes make the news, but primes in the range of, say, a few hundred digits are not something that anybody keeps track of. They are very easy to find -- the computer that's showing you this text is likely capable of finding at least several ones per second for you, and with overwhelming probability they will be primes nobody else have ever seen before.

There are very many hundred-digit primes to find. We could cover the Earth in harddisks full of distinct hundred-digit primes to a height of hundreds of meters, without even making a dent in the supply of hundred-digit primes.

This also raises the question of what it means that a prime is "known". If I generate a dozen hundred-digit primes and they are forgotten after I close the window showing them, are these primes still "known"? If instead I print out one of them and save the copy in a safe without showing it to anybody, is that prime "known"? What if I cast it into the concrete foundation for my new house?

$\endgroup$ 16 $\begingroup$

In order to get a rough estimate, I checked performance of PrimeQ function in Mathematica on my computer. It appears, that in order to calculate all primes up to $10^n$ using this function, I need $\approx11^{(n-6)} \mathrm{seconds}$ on my single core of amd athlon 7750. Then it would take me for example $\approx1500$ years to calculate all primes up to $10^{16}$, and as a result I would get $10^{14}$ primes.

As @Henning Makholm said

Nobody's really keeping count (of prime numbers).

It is probably because it is more efficient to calculate them when needed than to store them. And since for cryptography, only very large primes are important, no one really needs those small ones.

$\endgroup$ 1 $\begingroup$

I came across this interesting resource:

The first fifty million primes

Lists the first and last prime of sets of one million, and a more recent record:

New record prime (GIMPS): $2^{82,589,933}-1$

with 24,862,048 digits by P. Laroche, G. Woltman, A. Blosser, et al. (7 Dec 2018)

_{Source: The primes page (utm.edu)}

I also found the first 2 billion prime numbers, which isn't an academic site, but has links to some other prime databases.

$\endgroup$ 1 $\begingroup$

It turns out that an approximate answer can't even be computed by WolphramAlpha. I hope I got this right:

We start from the accepted answer to the question Finding the 2,147,483,647th prime number, which says that according to the prime number theorem there is

$$\pi(n)\approx\frac{n}{\log(n)}$$

where $\pi(n)$ is the number of prime numbers less than $n$. The largest known prime, discovered in 2008, is $2^{43,112,609}-1$, but if we put that in the place of $n$ we get an answer so big that not even WolframAlpha can compute $\pi(n)$ (no need to click on it, because it doesn't work).

However, we can still find an approximate answer thanks to the list of 10 largest known primes. The largest number for which WolframAlpha still works is currently ranking 3rd on that list and its value is $2^{37,156,667}-1$ from which we get that there are approximately $7.853*10^{11,185,263}$ (or $10^{10^{7.04865}}$) primes smaller than $2^{37,156,667}-1$ using the $\pi(n)$ formula.

$\endgroup$ 8