A50849. 超级素数在大于1的自然數中，除了1和它本身以外不再有其他因数的数，被称为素数，又叫质数。超级素数是指一个素数，每去掉最后一位上一个数字，总能保证剩下的数依然为素数。比如"373"就是一个超级素数，去掉个位的"3"后，"37"依然是素數：继续去掉"37"个位的"7"后，"3"还是素数。程序命名：prime.cpp输入：输人一个整数n（10<=n<=10^8）输出：输出所有小于等于n的超级素数的个数…
填空题
困难
知识点
题目描述
超级素数
在大于1的自然數中，除了1和它本身以外不再有其他因数的数，被称为素数，又叫质数。超级素数是指一个素数，每去掉最后一位上一个数字，总能保证剩下的数依然为素数。比如
"373"就是一个超级素数，去掉个位的"3"后，"37"依然是素數：继续去掉"37"个位的"7"后，"3"还是素数。
程序命名：prime.cpp
输入：输人一个整数n（10<=n<=10^8）
输出：输出所有小于等于n的超级素数的个数
样例输入1：
30
样例输出1：
6
样例输出1：
2 3 5 7 23 29
样例输入2：
50
样例输出2：
8
样例输出2：
2 3 5 7 23 29 31 37
参考答案
/*
算法思想
暴力枚举（70分）
可以通过线性筛素数法将所有不超过n的素数求出，
然后枚举每个素数，判断是否符合超级素数的性质。
时间复杂度 O(10^8)，最终70分，TLE。
DFS
分析超级素数的性质，会发现最高位只能由素数2 、 3 、 5 、 7组成，
其余各位只能从是奇数1 、 3 、 7 、 9 中选择，
因此可以使用DFS构造所有满足性质的超级素数。
*/
#include <iostream>
#include <cmath>
using namespace std;
int ans,n;
int a[]={2,3,5,7};//最高位
int b[]={1,3,7,9};//其他位
bool check(int x){//判断素数
if(x==1)return false;
for(int i=2;i<=sqrt(x);i++)
if(x%i==0) return false;
return true;
}
void dfs(int x){//深搜
if(x>n)return;
ans++;
for(int i=0;i<4;i++)
if(check(x*10+b[i]))
dfs(x*10+b[i]);
}
int main(int argc, char *argv[])
{
cin>>n;
for(int i=0;i<4;i++)
dfs(a[i]);
cout<<ans<<endl;
return 0;
}答案解析
上一题
下一题