Largest prime number?

Question

It was announced that the new largest known prime number was discovered. Can't a computer program just work it out with the press of a button?

Answer 1

Even on a fast computer, prime numbers are now so big that it takes a long time and lot of processing to establish whether or not a number is prime.

Answer 2

No, because they're not magic. Every operation a computer does takes time. That's why these prime numbers are somewhat important. Currently, there is no known way to generate prime numbers. So when a person can come up with a test or algorithm that can determine if a number is prime, then it means less stress on the computer components. The better the test, the less stress.



One of the most exhaustive methods would look at every prime number between 1 and sqrt(n), where n is the potential number. Prime distribution tends to follow (as a number grows larger and larger)



t / ln(t)



If we say that t = sqrt(n)



L = sqrt(n) / ((1/2) * ln(n))



This new prime number is 22,000,000 digits long (roughly). How many primes exist between 1 and 10^11000000?



L = 10^11000000 / ln(10^11000000)

ln(L) = 11000000 * ln(10) / ln(11000000 * ln(10))

ln(L) = 1485762 (roughly)

L = e^(1485762)

L = 10^(1485762 * log(e))

L = 10^645258, again, roughly



The 500 faster computers in the world have a combined speed of about 300 Petaflops per second, or 300 * 10^15 floating point operations per second. All of them working together would take:



10^645258 / (3 * 10^17) =>

(1/3) * 10^(645241) =>

3.333 * 10^645240 seconds



Now, you need to keep in mind a few things:



1) I have rounded down, twice, on orders of magnitude that are mind-confoundingly big

2) A floating point operation is not equivalent to performing an actual operation. It is much simpler. Checking the division of one number to another takes a lot of floating point operations, even for very small numbers. So I am still being extremely generous here



The universe is about 4.3 * 10^17 seconds old. If computers had to use that exhaustive method to find primes, then we'd be waiting through at least a few Poincare recurrence times before we got an answer.



EDIT:



I should amend my answer a bit. I said that there are currently no known way to generate primes and that's not true. What I meant to say was that there's no known way to generate a complete list of primes. However, a method of generating primes does exist



2

2 + 1 = 3

2 * 3 + 1 = 7

2 * 3 * 5 + 1 = 31

2 * 3 * 5 * 7 + 1 = 211

And so on.



Multiplying every known prime together and adding 1 generates prime numbers, just not a complete list. As you can tell, there are more than 5 primes between 2 and 211 and neither 5 or 7 were generated with that method.

Answer 3

No, because they're not magic. Every operation a computer does takes time. That's why these prime numbers are somewhat important. Currently, there is no known way to generate prime numbers. So when a person can come up with a test or algorithm that can determine if a number is prime, then it means less stress on the computer components. The better the test, the less stress.



One of the most exhaustive methods would look at every prime number between 1 and sqrt(n), where n is the potential number. Prime distribution tends to follow (as a number grows larger and larger)



t / ln(t)



If we say that t = sqrt(n)



L = sqrt(n) / ((1/2) * ln(n))



This new prime number is 22,000,000 digits long (roughly). How many primes exist between 1 and 10^11000000?



L = 10^11000000 / ln(10^11000000)

ln(L) = 11000000 * ln(10) / ln(11000000 * ln(10))

ln(L) = 1485762 (roughly)

L = e^(1485762)

L = 10^(1485762 * log(e))

L = 10^645258, again, roughly



The 500 faster computers in the world have a combined speed of about 300 Petaflops per second, or 300 * 10^15 floating point operations per second. All of them working together would take:



10^645258 / (3 * 10^17) =>

(1/3) * 10^(645241) =>

3.333 * 10^645240 seconds



Now, you need to keep in mind a few things:



1) I have rounded down, twice, on orders of magnitude that are mind-confoundingly big

2) A floating point operation is not equivalent to performing an actual operation. It is much simpler. Checking the division of one number to another takes a lot of floating point operations, even for very small numbers. So I am still being extremely generous here



The universe is about 4.3 * 10^17 seconds old. If computers had to use that exhaustive method to find primes, then we'd be waiting through at least a few Poincare recurrence times before we got an answer.



No. The only way for a computer to do it straightforwardly would be to take a number and divide it by all primes smaller than or equal to the number's square root. But various techniques have been developed for finding primes that are "too" big -- i.e., much larger than the squares of the known sequential primes. The latest large prime discovered has more than 22,000,000 digits. We do not KNOW all the primes with 11,000,000 digits or fewer, so we cannot test the prime status of a 22000000-digit number in a straightforward way.

Answer 4

No. The only way for a computer to do it straightforwardly would be to take a number and divide it by all primes smaller than or equal to the number's square root. But various techniques have been developed for finding primes that are "too" big -- i.e., much larger than the squares of the known sequential primes. The latest large prime discovered has more than 22,000,000 digits. We do not KNOW all the primes with 11,000,000 digits or fewer, so we cannot test the prime status of a 22000000-digit number in a straightforward way.

Answer 5

You need a lot of fine dividing and computers actually aren't too good with really big numbers, depends on the memory registers.

Answer 6

Fekefufu, stupid must be your nickname.