题目——梅森素数
时间限制:1000ms 内存限制:65536KB
题目描述
由于梅森学识渊博，才华横溢，为人热情以及最早系统而深入地研究2^(p) - 1 型的数（其中 p 为素数），为了纪念他，数学界就把这种数称为“梅森数”；并以 Mp 记之（其中M为梅森姓名的首字母），即Mp = 2^(p) - 1 。如果梅森数为素数，则称之为“梅森素数”。比如p＝2，3，5，7时， Mp 都是素数，但 2^(11) -1 不是素数 。现在把 p 的值告诉你, 请你判断这个 Mp 是不是素数。
输入
有1组测试数据。 第一行是一个正整数 T ，表示这一组测试数据的总个数。 接下来的每一行都是1个 p 的值，这里2 ≤ p ≤ 20。 这些总共会有 T 行。
输出
对于每个测试数据 p ，判断 Mp 是不是梅森素数，是就输 出“yes”，否就输出“no”，输出后请注意换行。
示例输入
2 2 7
示例输出
yes yes
题解
首先先给大家道个歉，由于我以为大家都打开了PC^2，所以就自作主张的在PC^2里面公示了题面更改和“请刷新浏览器”的信息，结果我错了=。=很多人都没看到=。=真惨。。。先给大家说声对不起了，第一次出题玩这个的确不熟练。。。
然后是正事：
我们都知道朴素的素数判断是O（根号n）的时间复杂度，就是说从3开始（偶数除了2以外全是合数，所以单独考虑2就行了），一直到根号n，进行遍历即可。那么对于这道题目，p最大20，也就是说最大的数据是2^20，可以在2^10次计算下完成，2^10 = 1024，也就是1000次运算，时间开销非常小。即便是纯暴力求解也毫无压力，因为我给的数据非常的弱。
发散一下：如果是多组数据但是不改变p的范围，最优的方法是打表法，我的标程就是这样的方法，同时用了一个小的优化，把时间复杂度优化到了
接着发散一下，如果改变p的范围，那就要用到米勒罗宾测试来求解了，具体的请自行百度吧！
代码示例
/****
*@PoloShen
*Title:D - NWPU SRM of 2013.Dec
*/
#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;
int Power(int a, int r){//整数乘方函数
if (r == 0) return 1;
else{
int res = 1;
for (int i = 0; i < r; ++i) res *= a;
return res;
}
return a;
}
inline int Gener(int p){//生成梅森数
return Power(2, p) - 1;
}
vector<int> Prime;int sz;
bool ans[25];
void set_Prime(){//建立素数表
Prime.clear();Prime.push_back(2);
for (int i = 3; i < 1100; i+=2){
bool flag = 1;
for (int j = 2; j < sqrt((double)i); ++j){
if ((i % j) == 0){flag = 0;break;}
}
if (flag) Prime.push_back(i);
}
sz = Prime.size();
return;
}
bool judge(int mp){//利用素数表判断素数
for (int i = 0; i < sz; ++i){
if (mp == Prime[i]) return 1; //如果与素数相同，即为素数
if ((mp % Prime[i]) == 0) return 0; //能够整除一素数，即为合数
}
return 1;
}
void set_table(){//建立梅森数表
for (int p = 2; p < 21; ++p){
int mp = Gener(p);
ans[p] = judge(mp);
}
return;
}
void solve(){//主要输入输出程序
int p;scanf("%d", &p);
if (ans[p]) printf("yes\n");
else printf("no\n");
return;
}
int main(){
set_Prime();
set_table();
int T;scanf("%d", &T);
while (T--){
solve();
}
return 0;
}
标准输入 |
标准输出 |
20 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2 20 |
yes yes no yes no yes no no no no no yes no no no yes no yes yes no |