Not how many are there (infinite, I believe), but how many have we found?

Perusing the net led me to this discussion on the topic, but despite my best efforts at interpreting it, the answer seems to range from around 10[sup]14[/sup] to around 10[sup]11,185,263[/sup].

A bit of a range there, or so it seems to me. Or maybe it’s just my inability to follow the discussion in the link.

Can anyone answer this question a bit more precisely?

It depends on what you mean by “find”. The 10[sup]11185263[/sup] number you cite is the (approximate) number of primes less than the largest known prime (as of 2008 – there have been higher ones found since) of 2[sup]37156667[/sup]-1. That doesn’t mean that every single one of those primes has been “found”.

Basically, we can “find” primes (especially Mersenne primes, of which 2[sup]37156667[/sup]-1 is one) that are very much larger than the list of primes that has been enumerated, or even the list of numbers that has ever been written down.

As for smaller primes (of only 100 decimal digits are so), computers generate these routinely as part of encryption algorithms and then throw them out unremarked when they are no longer needed. If that counts as a “find”, then we’re probably going to have to get into estimates of how much internet traffic there is in the world (and there is a lot, but probably not 10[sup]11185263[/sup] primes worth).

The total number of primes is indeed infinite, so there is no largest prime, but we can estimate fairly accurately, for any given X, how many integers below X are prime.

There’s no central registry keeping track of all discovered primes. Your PC is regularly generating new, almost certainly never generated before, primes in the context of setting up secure connections to other machines om the 'net. Those primes are only shared with the machine you’re connecting to, so we could try to estimate how many are being created globally in a given amount of time, but nobody has the complete list.

Probably the most relevant interpretation of your question would be “out of all the people who have run a prime sieve on a supercomputer to generate all the primes up to a given X, what is the largest X which has been achieved so far?” I don’t know the answer to that one but 10[sup]14[/sup] sounds like a plausible order-of-magnitude guess.

Actually, in you StackOverflow link, 10[sup]14[/sup] is somebody’s estimate for how many primes you could generate on a home PC in 1500 years, using Mathematica on single CPU core. 10[sup]11185263[/sup] is somebody else’s estimate for the number of primes smaller than the third-largest prime listed on Wikipedia. Neither of these numbers is the answer to your question.

I think the question isn’t quite right. You’re not really looking for an actual list of known primes; there are just too many possible ones (an infinite amount, right?) to keep any real list of all known primes. It’s not even possible to keep a real count; we’ve identified some really big primes, and there are just way too many primes between 2 and those big primes to go through and identify all of them (even just to count them, regardless of whether we make a list).

But we do know roughly how many primes there are in any given stretch of numbers. What people are answering in that linked thread is “How many primes, roughly, are there smaller than X”, for various different X’s.

So there are roughly 10^14 primes with sixteen or less decimal digits (which someone just chose kind of randomly as an upper limit). There’s some discussion about how many primes there are smaller than the largest currently known prime; it’s a simple formula, but the numbers are so big that, let’s face it, they don’t mean anything to either of us, other than ‘bigger than we can comprehend’.

If each of the eight billion people in the world owned a thousand computers, and each of those computers had been generating unique primes non-stop for the past 40 years at a rate of one million primes per second (which is unrealistically fast even for today’s state-of-the-art CPU’s, if you want the primes to be large enough for most of them to be unique) then all of us together would have generated 10[sup]28[/sup] primes by now. So yeah, probably not.

A simple proof that the number of primes is infinite:

Take all primes up to some allegedly highest prime, multiply them, and add 1. The result is prime, because the result is not divisible by any number up to the allegedly highest prime, or any prime higher than the highest known prime (other than the new one which is of course divisible by itself.)

This is a hypothetical prime generator, but an impractical one because finding all the primes up to the allegedly highest one is NP-complete (takes too long to be practicable on any computer with finite speed).

Good point: while it’s hard to say how many primes we’ve found, as there isn’t some list somewhere, we can at least put an upper bound on how many primes have been found.

Not quite. The result is either prime, or dividable by another prime which is larger than the “allegedly highest prime” which you started out with. So you have successfully proven that, for any prime P, there must exist another prime larger than P, and hence there cannot be a largest prime number.

However, there is no known method of generating a number which is sure to be prime, other than “pick plausible candidates and test them for prime-ness until you find one”.

I think the prime count can be calculated precisely for smallish bounds. For example, according to this page, there are 1,699,246,750,872,437,141,327,603 prime numbers with 25 decimal digits or less. That’s 1 septillion 699 sextillion 246 quintillion 750 quadrillion 872 trillion 437 billion 141 million 327 thousand 603, so obviously wasn’t found by brute enumeration. (Validity may depend on Riemann’s Hypothesis.)

Prime Obsession by John Derbyshire is a good book addressing this and related questions that both laymen and experienced mathematicians may appreciate.

Walton Firm already dealt with this, but to re-iterate: The result certainly could be composite and divisible by a prime higher than the highest prime on the original list. For example, the first six primes are 2, 3, 5, 7, 11, and 13. Multiplying these together and adding 1, we get 30031. But 30031 isn’t prime; its prime factorization is 59 * 509.

I will second that, but probably it is of more interest to a mathematician (except for number theorists who already know all of it) than to others. He does try to render it accessible to non-mathematicians (of which he is one), but only partially succeeds. He does explain very carefully how to get the exact number of primes below a given number, but it is quite complicated. A good estimate is given by the prime number theorem: x/(ln x).

Thanks for the explanations of the various scenarios. From here on I will consider that there are TNTC[sup][/sup] prime numbers known.
[sub][sup][/sup]Too Numerous To Count[/sub]

It’s also worth mentioning that the multitude of primes routinely found by computers going about their ordinary business aren’t actually verified to be primes. They’re tested probabilistically, and only used if there’s a really, really high chance that they’re actually primes (like, one in a trillion that they’re not, maybe), but actual 100% verification is enough slower that it’s not usually worth bothering with (though not so slow that it’s unfeasible, if for some reason you want that).

So let’s try a slightly different question related to this. I presume there’s a list somewhere of all the primes for smaller numbers. So what is the percentage of primes in a specified range?

primes in 1…10 (2,3,5,7) = 40% (I can do this one)
primes in 1…100?
primes in 1…1000?
primes in 1…10,000?
etc.

Seems to me that it would be a declining percentage. Does plotting this percentage give any kind of an interesting curve?

Welcome to the Prime Number Theorem. An approximation to this curve was known by 1800, but proving it correct was, like Fermat’s Last Theorem, a mathematician’s Holy Grail for another century. “The theorem was proved independently by Jacques Hadamard and Charles Jean de la Vallée-Poussin in 1896 using ideas introduced by Bernhard Riemann.”