Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
9  
Luis Silvestre has a list of all prime numbers. It can be browsed but not downloaded. –  user53153 Jan 8 '13 at 13:21
1  
$\infty$ perhaps? –  nbubis Jan 8 '13 at 13:27
1  
@PavelM: No he hasn't, even if he claims so. And this is not what I call browsing (can I have the last page please?). –  Marc van Leeuwen Jan 8 '13 at 15:10
    
@nbubis: I asked about known primes. –  f.ardelian Jan 8 '13 at 17:53
    
This is a more interesting question from an historical perspective (i.e. before computers): see primes.utm.edu/glossary/xpage/TablesOfPrimes.html for a list of published tables of primes. –  Douglas S. Stones Jan 9 '13 at 8:35

4 Answers 4

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?

share|improve this answer
11  
If a prime were to fall down in a forest and nobody heard it, would it make a sound? –  coffeemath Jan 8 '13 at 14:16
1  
(2) Here's another way to look at it: how many known odd positive numbers are smaller than Graham's number? The answer to that would be (g64+1)/2. They can't be listed but we have a relatively simple way of expressing how many they are. –  f.ardelian Jan 9 '13 at 3:08
1  
@f.ardelian: We have a good way of expressing $\pi(n)$, the number of primes less than $n$, but as the numbers get large we don't know which ones are prime. Your question seemed to be interested in which ones are prime. For any given number, we can check it reasonably easily if it is less than $10^{200} $ (say), but there are so many we can't check them all. –  Ross Millikan Jan 9 '13 at 5:32
1  
@5PM, the sum of the first 1 million prime reciprocals is 2.88733 and Mathematica is still running on my laptop to add 10m of them. –  alancalvitti Feb 7 '13 at 15:29
2  
@5PM, I was at a talk some years ago where the speaker said, "The sum of the reciprocals of all known primes is less than $4$, and always will be." –  Gerry Myerson Feb 8 '13 at 5:16

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.

share|improve this answer
    
A sieve is much more efficient yet. It takes a second or two to build a table of primes up to $10^8$. One could easily use this to compute all the primes up to $10^{16}$ in a matter of weeks rather than centuries (but yes, storing them is another matter). –  Erick Wong Feb 7 '13 at 15:20

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.

share|improve this answer
1  
Dear f.ardelian, There is something strange with your claim about computing $\pi(n)$, because if you can write down $n$ --- which you can, you just wrote that it's $2^{43,112,609} - 1$, then you can write down $\log n$ --- its roughly $30,000,000$ --- and then you can compute $n/\log n$ --- it's roughly $2^{43,112,584}$. Regards, –  Matt E Jan 9 '13 at 4:00
    
The asymptotic formula for $\pi(n)$ does not require $n$ to be prime. I can plug in $$n=10^{10^{10^{10^{10^{10}}}}}$$ and get $$\pi(n)\approx (\log(10) )^{-1}\cdot 10^{10^{10^{10^{10^{10}}}}-10^{10^{10^{10}}}}$$ –  user53153 Jan 9 '13 at 4:33
2  
This ignores OP's point (a good one) that there are many primes below the few largest known that are not themselves known. –  Ross Millikan Jan 9 '13 at 5:26
    
@MattE Are you sure? According to WolframAlpha, $\log(2^{43,112,609}) \approx 2.988*10^{7}$ wolframalpha.com/input/?i=log%282%5E43%2C112%2C584-1%29 –  f.ardelian Jan 9 '13 at 14:25
2  
Only a ridiculously small fraction of those $10^{10^7}$ primes are "known" (in any meaningful way), though. –  Henning Makholm Feb 7 '13 at 19:04

With Cryptography in mind I suspect that agencies like NSA and GCHQ have been listing not just primes, but all the combinations of multiplying primes ever since james ellis came up with public key cryptography in 1973. You can crunch a lot of numbers in 40 years.

share|improve this answer
6  
This is just speculation on your part though. It should probably be a comment since it doesn't actually answer the question. –  Henry T. Horton May 14 '13 at 1:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.