Large Prime Numbers
Date: 01/13/2009 at 13:10:02 From: Dave Subject: Large primes What is the largest prime number less than which all primes are known? (We might call this the largest "contiguous" prime.) I haven't been able to find this out on the web. There is a lot of discussion about the largest primes known, of course, but not on "contiguous" primes. Presumably this list is always changing, but I'm trying to find out how high that list goes right now.
Date: 01/13/2009 at 15:43:50 From: Doctor Vogler Subject: Re: Large primes Hi Dave, Thanks for writing to Dr. Math. Answering that question is more a matter of figuring out what you consider "known" than solving a math problem. Using the Sieve of Eratosthenes (or a modern variation known as the Sieve of Atkins), computers can generate consecutive prime numbers faster than they can store them to disk. You can download lists of primes, but when you want a really long list, it's faster to download a program that will generate the list for you. If by "known" you mean that some human knows that this particular number is prime, then I'm sure the largest contiguous prime is quite small. If by "known" you mean that there is a list of primes stored on some computer disk up to this number, then it's probably somewhere in the trillions. But that number would be subject to change, because the person who used several terabytes of disk storage to save the list probably didn't do so just to make a record; he was probably using them. And when he is done with them, then he is likely to delete the list and use those terabytes of storage for something else. You can get a lower bound for this number by downloading a prime number generator and filling up your own hard disk with primes. If by "known" you mean that some computer program at some point generated all primes up to this number but, due to a lack of space to store them all, didn't record the full list, then it might be in the hundreds or thousands of trillions, but it would be hard to find this out and harder still to substantiate/verify someone's claim of having computed all primes up to some huge number. And why would you bother to compute them if you weren't going to store them? Only if you had need of a longer list of consecutive primes than you were willing or able to store to disk. Certainly, the number is smaller than the trillions-of-trillions range, since even the more efficient Sieve of Atkins takes O(n) operations to find the primes up to n, and a trillion trillion is 10^24 (or about 2^80). Well, a modern computer might run around 4 GHz, or 4 * 10^9 operations per second, or about 1.26 * 10^17 operations per year. So it would take a million computers running at 4 GHz for almost 10 years to do 10^24 operations, and I don't think anyone is going to use that kind of resource for that long generating prime numbers. On the other hand, testing a single number around 2^80 (or even much larger than that) is very fast and can be done in a fraction of a second on a computer. But numbers with many more digits take a lot longer to verify that they are prime. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Date: 01/13/2009 at 18:26:36 From: Dave Subject: Thank you (Large primes) Thank you! This was very helpful.
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.