大意不再赘述。
思路:我用的Lucas_Lehmer测素数法。
具体流程:设要确定的素数为Mp = 2^p-1,则令LUCAS序列data[1] = 4, L(i) = (L(i-1)^2 - 2) % Mp,Mp = 2^p - 1,如果data[p-1] == 0的话,则该数为梅森素数。
算法的简单证明:Lucas_Lehmer
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> using namespace std; typedef long long LL; LL Mul(LL a, LL b, LL m) { LL ans = 0; while(b) { if(b & 1) ans = (ans + a) % m; a = (a*2)%m; b /= 2; } return ans; } LL data[70]; int Lucas_Lehmer(int p) { LL MOD = (1LL<<p)-1; data[1] = 4; for(int i = 2; i <= p-1; i++) { LL ans = Mul(data[i-1], data[i-1], MOD); data[i] = (ans-2) % MOD; } if(data[p-1] == 0) return 1; return 0; } void solve() { LL n; scanf("%lld", &n); if(n == 2) { printf("yes\n"); return ;} if(Lucas_Lehmer(n)) printf("yes\n"); else printf("no\n"); } int main() { int T; scanf("%d", &T); while(T--) { solve(); } return 0; }