题目描述
质数 7331,当删除个位时,剩下三位构成质数733,再删除个位,剩下两位构成质数73,再删除一位,最后剩下一个数构成质数7。像7331这样的数字我们可以称之为长度为4的超级质数。现在给定一个整数N,请你求出长度为N的超级质数有哪些。数字 1 不是质数。
样例
输入样例:
4
输出样例:
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393
算法1
(BFS)
C++ 代码
//1.长度为1的质数只有2,3,5,7将一位质数作为起点
//2.长度比1大的质数都是以1,3,7,9结尾的(也就是扩展路径),因此每次
// 扩展时只需判断是否合法,如果合法则入队
#include <iostream>
#include <queue>
using namespace std;
int l,r;
int a[] = {1,3,7,9};//模拟扩展路径
bool check(int x)//如果x是质数则返回 true
{
if(x == 1) return false;
for(int i = 2; i <= x / i; i++)
if(x % i == 0)
return false;
return true;
}
void BFS()
{
queue<int> q;
q.push(2),q.push(3),q.push(5),q.push(7);//起点入队
while(q.size())
{
int t = q.front();
q.pop();
if(t > r) break;//剪枝
if(t >= l && t <= r) cout << t << endl;//如果在区间内则输出
for(int i = 0; i < 4; i++)
{
t = t * 10 + a[i];
if(check(t))
q.push(t);
t /= 10;//状态恢复
}
}
}
int main()
{
int n;
cin >> n;
l = 1;
for(int i = 1; i < n; i++) l *= 10;
r = l * 10 - 1;//构造区间端点
BFS();
return 0;
}
算法2
(打表)
一开始是写了一个DFS的当时间复杂度很高,输入8时程序跑了大约半个小时才跑出结果,所以就又想到了打表
C++ 代码
#include <iostream>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
if(n == 1) printf("2\n3\n5\n7\n");
else if(n == 2) printf("23\n29\n31\n37\n53\n59\n71\n73\n79\n");
else if(n == 3) printf("233\n239\n293\n311\n313\n317\n373\n379\n593\n599\n719\n733\n739\n797\n");
else if(n == 4) printf("2333\n2339\n2393\n2399\n2939\n3119\n3137\n3733\n3739\n3793\n3797\n5939\n7193\n7331\n7333\n7393\n");
else if(n == 5) printf("23333\n23339\n23399\n23993\n29399\n31193\n31379\n37337\n37339\n37397\n59393\n59399\n71933\n73331\n73939\n");
else if(n == 6) printf("233993\n239933\n293999\n373379\n373393\n593933\n593993\n719333\n739391\n739393\n739397\n739399\n");
else if(n == 7) printf("2339933\n2399333\n2939999\n3733799\n5939333\n7393913\n7393931\n7393933\n");
else printf("23399339\n29399999\n37337999\n59393339\n73939133\n");
return 0;
}