蓝桥杯 adv149 质数的肋骨

蓝桥杯 adv149 质数的肋骨

问题描述

农民约翰母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数。

例如有四根肋骨的数字分别是:7 3 3 1,那么全部肋骨上的数字 7331是质数;三根肋骨 733是质数;二根肋骨 73 是质数;当然,最后一根肋骨 7 也是质数。7331 被叫做长度 4 的特殊质数。

写一个程序对给定的肋骨的数目 N (1<=N<=8),求出所有的特殊质数。数字1不被看作一个质数。

输入格式

单独的一行包含N。

输出格式

按顺序输出长度为 N 的特殊质数,每行一个。

样例输入

4

样例输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

参考解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>

using namespace std;

int prim[10000];
int n;

void dfs(int num, int depth) {
if (depth == n)
cout << num << endl;
for (int i = 0; i < 9; ++i) {
if (prim[num*10+i] == 0)
dfs(num * 10 + i, depth+1);
}
}

int main() {
prim[0] = 1;
prim[1] = 1;
for (int i = 2; i < 100; ++i) {
if (prim[i] == 1) continue;
for (int j = i * i; j < 10000; j+=i)
prim[j] = 1;
}
cin >> n;
dfs(0, 0);
return 0;
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×