c++程序 梅森素数 一直超时 有没有快速算法？？

Question

如题所述

Answer 1

这个是有专门的检验算法的。 目前最好的算法是：Lucas–Lehmer（卢卡斯-莱默）算法。

所以你不用从2～开始逐个穷尽。。。。 但2^p很快就会变的非常大，普通的函数库会溢出的，需要用到能处理大数的函数库，但p变大时，计算时间也相应变长。。。。

下面是p ≤ 32时的小范围梅森数的检验代码（没有用到c++的类概念设计）

#include <iostream>
#include <cmath>

using namespace std;

bool isPrime(const int n);
bool isMersennePrime(const int n);

int main(int argc, char const *argv[])
{
    cout << "Mersenne Primes: " << endl;
    for (int i = 2; i <= 32; i +=1)
        if (isPrime(i) && isMersennePrime(i) )
            cout << " " << i;

    cout << endl;    
    return 0;
}

bool isPrime(const int n)
{
    if (n == 2)    return true;
    else if (n <=1 || n % 2 == 0) return true;

    bool prime = true;
    const int sqr = sqrt(n);
    for (int i = 3; i  <= sqr; i += 2)
        if ( !(prime = n % i) ) break;

    return prime;
}

bool isMersennePrime(const int p)
{
    if (p == 2) return true;
    const long long unsigned  m_p = ( 1LLU << p) - 1;
    long long unsigned  s = 4;
    for (int i = 3; i <= p; ++i)
        s = (s * s - 2) % m_p;
    
    return (s == 0);
}

运行：

Mersenne Primes:
 2 3 5 7 13 17 19 31

Answer 2

把你的代码贴上来

Answer 3

你是用什么软件计算出你程序运行的时间的?