20081124, 10:40  #1 
Sep 2008
7 Posts 
Method of Euclid's Proof
I was wondering why the method of Euclid's proof isn't used to find world's largest primes...
To find a new prime,you could just multiply all primes up to a certain number, and then add one. If you're sure you didn't miss a prime you've found a new one. maybe the primes found this way don't grow fast enough? I'm probably missing a simple thing. 
20081124, 10:50  #2  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
5,879 Posts 
Quote:
After having done all the multiplies and added 1 now how do you know if the result is a prime? You need some sort of test to determine if your number is prime. Not as easy as it might seem. And even if you determine it is not prime, how do you find the divisors? Again you need some sort of method to extract the necessary information. It is not good enough just to say "Oh, there is a new prime in there somewhere, but I don't know what it is". Last fiddled with by retina on 20081124 at 10:51 

20081124, 11:17  #3  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
23722_{8} Posts 
Quote:
2*3*5*7*11*13 + 1 = 30031 59 * 509 = 30031 Paul 

20081124, 13:32  #4 
Feb 2006
Denmark
2·5·23 Posts 
This is based on a common misunderstanding of Euclid's proof. As Xilman's example shows, there are actually two possiblities: The number may be prime or it may be composite with prime factors which are larger than the multiplied primes. In the vast majority of tested cases, and probably almost all cases, it is the second possibility. Then there is no known feasible method to find the large prime factors.

20081129, 20:27  #5  
Aug 2006
13462_{8} Posts 
Finding a new prime is easy. I put
Code:
nextprime(random(10^65)) 70486640254630306486542498129083911644039810089312084380333291127 (I then verified this in about twotenths of a second with isprime(%)), a prime that in all likelihood no one has ever seen before. Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Euclid, the game  VBCurtis  Puzzles  0  20150309 04:28 
Euclid Mullin  henryzz  Factoring  1  20131227 01:37 
second EuclidMullin sequence  arbooker  Factoring  52  20131203 23:00 
Euclid's proof of the infinite number of primes  troels munkner  Miscellaneous Math  43  20100906 01:36 
Euclid sequences  Maybeso  Math  2  20030808 17:55 