USACO Section 1.5: Superprime Rib
6909 ワード
1 /*
2 ID: leetcod3
3 PROG: sprime
4 LANG: C++
5 */
6 #include <iostream>
7 #include <fstream>
8 #include <string>
9 #include <map>
10 #include <vector>
11 #include <set>
12 #include <algorithm>
13 #include <queue>
14 #include <cmath>
15 #include <list>
16 #include <cstring>
17 #include <cstdlib>
18 #include <limits>
19 #include <stack>
20
21 using namespace std;
22
23 ofstream fout ("sprime.out");
24 ifstream fin ("sprime.in");
25
26 vector<int> ans;
27 int N;
28
29 bool prime(int x) {
30 if (x == 2) return true;
31 for (int i = 2; i <= (int)sqrt(x*1.0); i++) {
32 if (x % i == 0) return false;
33 }
34 return true;
35 }
36
37 void dfs(int x, int cur) {
38 if (cur == N) {
39 ans.push_back(x);
40 return;
41 }
42 for (int i = 1; i < 10; ++i) {
43 int tmp = x*10;
44 tmp += i;
45 if (prime(tmp)) dfs(tmp, cur+1);
46 }
47 }
48
49 int main()
50 {
51 fin >> N;
52 for (int i = 2; i < 10; ++i) {
53 if (prime(i)) dfs(i, 1);
54 }
55 sort(ans.begin(), ans.end());
56 for (int i = 0; i < ans.size(); i++) fout << ans[i] << endl;
57 return 0;
58 }