mersenneforum.org > Math How did Prof.Cole factor M67?
 Register FAQ Search Today's Posts Mark Forums Read

 2020-02-07, 16:26 #34 JeppeSN     "Jeppe" Jan 2016 Denmark 2×71 Posts forprime(p=2,2^(67/2),(2^67-1)%p==0&&return(p)) (PARI/GP) That is the worst method I can imagine. It tries every prime (ignoring the fact that Mersenne divisors have a special form), it even recalculates 2^67 every time without modular optimization. And still you have the answer in less than 5 seconds on a slow machine. OK, the primes were pre-sieved. If you try all whole numbers, it actually becomes kind of slow (over a one minute on my slow machine): for(p=2,2^(67/2),(2^67-1)%p==0&&return(p)) Any slower? /JeppeSN
2020-02-07, 16:38   #35
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

2·532 Posts

Quote:
 Originally Posted by JeppeSN Any slower?
Slower is easier to achieve than faster.

Work your way downwards, trial divide from 2^67-2 to sqrt(2^67).

 2020-02-08, 02:59 #36 CRGreathouse     Aug 2006 16EA16 Posts There is a glorious algorithm proudly posted on Stack Overflow: Code: isPrime(testNum) { if ( testNum <= 1 ) return false; for ( primeFactor = 2; primeFactor < testNum; primeFactor++ ) if ( isPrime(primeFactor) ) if ( testNum % primeFactor == 0 ) return false; return true; } which could be adapted for this purpose. It would take over 10^978123027341497027 recursive calls to isPrime() to determine the primality of 2^67-1 with this algorithm.
2020-02-08, 03:49   #37
bsquared

"Ben"
Feb 2007

CCC16 Posts

Quote:
 Originally Posted by CRGreathouse There is a glorious algorithm proudly posted on Stack Overflow: Code: isPrime(testNum) { if ( testNum <= 1 ) return false; for ( primeFactor = 2; primeFactor < testNum; primeFactor++ ) if ( isPrime(primeFactor) ) if ( testNum % primeFactor == 0 ) return false; return true; } which could be adapted for this purpose. It would take over 10^978123027341497027 recursive calls to isPrime() to determine the primality of 2^67-1 with this algorithm.
That... is a work of art. Finely crafted inefficiency.

2731988490 calls to prove 127 prime.

Last fiddled with by bsquared on 2020-02-08 at 04:54

 Similar Threads Thread Thread Starter Forum Replies Last Post ET_ FermatSearch 2 2016-11-03 17:00 lfm Data 15 2010-03-30 21:18 fivemack ElevenSmooth 4 2008-05-07 19:28 matt00926 Hardware 3 2005-03-16 00:15 dsouza123 Software 12 2003-08-21 18:38

All times are UTC. The time now is 01:33.

Tue Aug 11 01:33:48 UTC 2020 up 24 days, 21:20, 1 user, load averages: 1.79, 1.75, 1.65