Look up the article on Wikipedia.
If you follow the article exactly, the loop should be
for (int i = 1; i <= exp - 2; ++i)
That's exp - 2 iterations of the loop. Yours only iterates exp - 3 times.
문제
I am currently writing a C++ program to find Mersenne prime numbers, utilizing the ttmath api on MS Win8.1. I have written the Lucas-Lehmer algorithm, but whatever value I try I always get a no-Mersenne-number message. Can somebody point out the error in my Lucas-Lehmer algorithm?
void LLIteration::calculate()
{
ttmath::UInt<100> num = 2;
ttmath::UInt<100> s = 4;
(num.Pow(this->exp));
num = num-1;
for(int i = 3; i < exp; ++i){
s = (s*s-2) % num;
std::cout << s << std::endl;
}
if(s == 0){
std::cout << "Found Mersenne prime, 2^" << exp << " = " << num << std::endl;
} else {
std::cout << "no prime 2^" << exp << " = " << num << std::endl;
}
}
Like I said, I always get the no prime message, and I cannot figure out why. Exp is an int representing the power to raise 2 to, and the rest is pretty straightforward.
Thanks in advance!
해결책
Look up the article on Wikipedia.
If you follow the article exactly, the loop should be
for (int i = 1; i <= exp - 2; ++i)
That's exp - 2 iterations of the loop. Yours only iterates exp - 3 times.