c++ - 使用 Lucas-Lehmer 迭代查找梅森数

Question

我目前正在编写一个 C++ 程序来查找 Mersenne 素数，利用 MS Win8.1 上的 ttmath api。我已经编写了 Lucas-Lehmer 算法，但无论我尝试什么值，我总是得到一条无梅森数的消息。有人可以指出我的 Lucas-Lehmer 算法中的错误吗？

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;
    }
}

就像我说的，我总是收到 no prime 消息，但我不明白为什么。 Exp 是一个整数，表示 2 的乘方，剩下的就很简单了。

提前致谢!

Answer 1

在维基百科上查找文章。

如果你完全按照这篇文章，循环应该是

for (int i = 1; i <= exp - 2; ++i)

这是 exp - 循环的 2 次迭代。你的只迭代 exp - 3 次。