Posted on 2009-03-23 11:52
superman 阅读(88)
评论(0) 编辑 收藏 引用 所属分类:
USACO
1 #include <math.h>
2 #include <iostream>
3
4 using namespace std;
5
6 bool isPrime(int n)
7 {
8 if (n == 1)
9 return false;
10 if (n == 2)
11 return true;
12 for (int i = 3; i <= (int)sqrt(n); i += 2)
13 if (n % i == 0)
14 return false;
15 return true;
16 }
17
18 void generateSuperprime(int i, int n, int cur)
19 {
20 if (i == n)
21 {
22 cout << cur << endl;
23 return;
24 }
25 if (i == 0)
26 {
27 generateSuperprime(i + 1, n, 2);
28 generateSuperprime(i + 1, n, 3);
29 generateSuperprime(i + 1, n, 5);
30 generateSuperprime(i + 1, n, 7);
31 }
32 else
33 {
34 if (isPrime(cur * 10 + 1))
35 generateSuperprime(i + 1, n, cur * 10 + 1);
36 if (isPrime(cur * 10 + 3))
37 generateSuperprime(i + 1, n, cur * 10 + 3);
38 if (isPrime(cur * 10 + 7))
39 generateSuperprime(i + 1, n, cur * 10 + 7);
40 if (isPrime(cur * 10 + 9))
41 generateSuperprime(i + 1, n, cur * 10 + 9);
42 }
43 }
44
45 int main()
46 {
47 freopen("sprime.in", "r", stdin);
48 freopen("sprime.out", "w", stdout);
49
50 int n;
51
52 cin >> n;
53 generateSuperprime(0, n, 0);
54
55 return 0;
56 }
57