View Single Post
2020-02-08, 03:49   #37
bsquared

"Ben"
Feb 2007

22·32·7·13 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