View Single Post
Old 2020-02-08, 03:49   #37
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22·32·7·13 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.

[edit]
2731988490 calls to prove 127 prime.

Last fiddled with by bsquared on 2020-02-08 at 04:54
bsquared is offline   Reply With Quote