Mp = 2^p-1 且 p是素数，称为梅森数，若Mp是素数则称为梅森素数。
Lucas-Lehmer判定法 判定一个数是否为梅森素数 效率足够高，如果题目特意为梅森素数设计，会卡复杂度，那么套用此方法即可。算法复杂度为O(p^3)。 关于卢卡斯-莱默算法参考http://blog.csdn.net/cFarmerReally/article/details/52153410?locationNum=7&fps=1
思路：R.1 = 4;R.k = (R.k-1 ^ 2 - 2) % Mp;
如果R.p-1 == 0，则是梅森素数，否则不是。
特殊判断,p == 2，即Mp = 3是梅森素数。
为了乘法溢出可以采用换加法来处理。 梅森素数表：因为个数不多所以常常可以打表 相关拓展：完美数，华林问题，蔡天新的课程
可以做模板来使用了：
long long multi(long long a, long long b, long long m){//实现a * b % m的操作,用2 * 3 = 6模拟一下就懂了 long long ans = 0; while(b > 0){ if(b & 1) ans = (ans+a) % m; b >>= 1; a = (a<<1) % m; } return ans; } //判断是否是梅森素数 bool is_msPrime(int p){ long long r[70]; long long m = 1; m <<= p; m -=1;//求出Mp; r[1] = 4LL; if(p == 2) return true; for(int i = 2; i <= p-1; ++i) r[i] = (multi(r[i-1],r[i-1],m)-2) % m; if(r[p-1] == 0) return true; return false; }nefu120
题意：判断第p个梅森数就否为梅森素数，p <= 62;
lucas-lehmer 判定：
#include<iostream> #include<cstdio> using namespace std; typedef long long ll; const int maxn = 63; ll multi(ll a,ll b,ll mod_val)//实现a * b % mod_val的操作 { a = a % mod_val; b = b % mod_val; ll ans = 0; while(b) { if(b & 1) { ans = (ans + a) % mod_val; } b >>= 1; a = (a <<= 1) % mod_val; } return ans; } bool is_meiprime(ll n,int p) { ll t = 4; for(int i = 2; i <= p - 1; i ++)//求出R[p - 1] { t = (multi(t,t,n) - 2 ) % n ; } t %= n; if(t == 0) return true; return false; } int main() { int Tcase; scanf("%d",&Tcase); for(int ii = 1; ii <= Tcase; ii ++) { int p; scanf("%d",&p); if(p == 2)//当为2的时候需要特判 { cout << "yes" << endl; continue; } ll sum = 1; sum <<= p; sum --;//sum 为求出的梅森数 if(is_meiprime(sum,p)) cout << "yes" << endl; else cout << "no" << endl; } return 0; } miller-rabin判定： #include<iostream> #include<cstdio> #include<stdlib.h> #include<ctime> using namespace std; typedef long long ll; const int maxn = 63; // a * b % n //例如: b = 1011101那么a * b mod n = (a * 1000000 mod n + a * 10000 mod n + a * 1000 mod n + a * 100 mod n + a * 1 mod n) mod n ll mod_mul(ll a, ll b, ll n) { ll res = 0; while(b) { if(b&1) res = (res + a) % n; a = (a + a) % n; b >>= 1; } return res; } //a^b % n //同理 ll mod_exp(ll a, ll b, ll n) { ll res = 1; while(b) { if(b&1) res = mod_mul(res, a, n); a = mod_mul(a, a, n); b >>= 1; } return res; } bool miller_rabin(ll n) { if(n == 2 || n == 3 || n == 5 || n == 7 || n == 11) return true; if(n == 1 || !(n%2) || !(n%3) || !(n%5) || !(n%7) || !(n)) return false; ll x, pre, u; int i, j, k = 0; u = n - 1; //要求x^u % n while(!(u&1)) { //如果u为偶数则u右移，用k记录移位数 k++; u >>= 1; } int S = 20; srand((ll)time(0)); for(i = 0; i < S; ++i) { //进行S次测试 x = rand()%(n-2) + 2; //在[2, n)中取随机数 if((x%n) == 0) continue; x = mod_exp(x, u, n); //先计算(x^u) % n， pre = x; for(j = 0; j < k; ++j) { //把移位减掉的量补上，并在这地方加上二次探测 x = mod_mul(x, x, n); if(x == 1 && pre != 1 && pre != n-1) return false; //二次探测定理，这里如果x = 1则pre 必须等于 1，或则 n-1否则可以判断不是素数 pre = x; } if(x != 1) return false; //费马小定理 } return true; } int main() { int Tcase; scanf("%d",&Tcase); for(int ii = 1; ii <= Tcase; ii ++) { int p; scanf("%d",&p); ll sum = 1; sum <<= p; sum -= 1; if(miller_rabin(sum)) cout << "yes" <<endl; else cout << "no" << endl; } return 0; }
