对于一个素数a，2^a-1叫做梅森数。 如果2^a-1为素数则叫做梅森素数。
我们知道，如果a为合数，则2^a-1一定不是素数。
2^a-1为素数，则a必为素数。
如果a为素数，则2^a-1可为素数，也可为合数。
unsigned long long multi_pow(unsigned long long x,unsigned long long x1,unsigned long long mod) { unsigned long long sum=0; while(x1) { if(x1&1) sum = (sum+x)%mod; x1 >>= 1; x = (x<<1)%mod; } return sum; } bool check_primemason(int n) //测试2^n-1 是不是素数 { unsigned long long r=4; unsigned long long mod=(unsigned long long)(1LL<<n)-1; for(int i=2;i<n;i++) { r=multi_pow(r,r,mod); r = (r-2+mod)%mod; } if(n==1) return 0; if(n==2) return 1; if(r==0) return 1; return 0; }
原文：http://www.cnblogs.com/chenhuan001/p/4982635.html