梅森素数VS是（四）素数
梅森素数
查看题解 查看答案
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
关于梅森素数。所谓梅森数，是指形如2^p-1的一类数，其中指数p是素数，常记为M(p)。如果p是素数的同时，梅森数（即2^p-1)也是素数，就称这个梅森数为梅森素数。输入一个长整型数n，输出不大于它的所有梅森素数。
输入输出格式
输入描述:
输入一个长整型数
输出描述:
输出比该数字小的梅森素数
输入输出样例
输入样例#:
1000
输出样例#:
M(2)=3 M(3)=7 M(5)=31 M(7)=127
题目来源
华中科技大学机试题
代码参考：
#include<bits/stdc++.h> using namespace std; int fun(long n){ if(n <= 1) return 0; for(int i = 2; i * i <= n; i ++){ if(n % i == 0){ return 0; } } return 1; } int main(){ long n; cin>>n; int count = 0; for(int i = 2; i < n; i ++){ long long p = pow(2, i) - 1; if(p > n){ break; } if(fun(i) && fun(p)) { cout<<"M("<<i<<")="<<p<<endl; } } return 0; }是（四）素数
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
对一个素数，若其含有4，则称其为四素数，如41，149就是四素数，问1e7以内四素数有多少个。
输入输出格式
输入描述:
无
输出描述:
1e7以内四素数的个数
输入输出样例
输入样例#:
无
输出样例#:
无
题目来源
天津大学机试题
代码参考：
#include<bits/stdc++.h> using namespace std; int result[10000001] = {0};//标记为素数 int fun4(long n){ while(n){ int temp = n % 10; if(temp == 4){ return 1; } n = n / 10; } return 0; } int main(){ long n = 1e7; result[1] = 1;//1先标记为合数 for(int i = 2; i * i <= n; i ++){ if(result[i] == 0){//是素数 for(int j = i * i; j <= n; j += i){//i的倍数标记为合数 result[j] = 1; } } } int count = 0; for(int i = 2; i <= n; i ++){ if(result[i] == 0 && fun4(i)) { count ++; } } cout<<count<<endl; return 0; }
《考场素数武器判决书》
看题目范围 <= 1e7（一千万），且要求求“一段区间/一共多少个”：
👉无脑选【打表法 / 埃氏筛法】！（在全局区开大数组，防止 TLE 超时）。
看题目范围 >= 1e7（或者十几亿、长整型），或者只问“某几个指定的数字是不是素数”：
👉无脑选【单体开平方试除法】！（极其省内存，防止 MLE 爆内存闪退）。