mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2020-02-07, 16:26   #34
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2·71 Posts
Default

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
JeppeSN is offline   Reply With Quote
Old 2020-02-07, 16:38   #35
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×532 Posts
Default

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

Work your way downwards, trial divide from 2^67-2 to sqrt(2^67).
retina is offline   Reply With Quote
Old 2020-02-08, 02:59   #36
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·7·419 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
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
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Got an email from prof. Keller ET_ FermatSearch 2 2016-11-03 17:00
big factor lfm Data 15 2010-03-30 21:18
New factor fivemack ElevenSmooth 4 2008-05-07 19:28
Prime 95 + BSOD issues Win xp Prof sp2 matt00926 Hardware 3 2005-03-16 00:15
Shortest time to complete a 2^67 trial factor (no factor) dsouza123 Software 12 2003-08-21 18:38

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

Tue Aug 11 01:03:07 UTC 2020 up 24 days, 20:49, 1 user, load averages: 1.74, 1.80, 1.64

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.