Posted on 2009-03-22 16:07
superman 閱讀(152)
評論(0) 編輯 收藏 引用 所屬分類:
USACO
1 #include <math.h>
2 #include <iostream>
3
4 using namespace std;
5
6 int ansCnt, ansNum[50000];
7
8 bool isPrime(const int n)
9 {
10 if (n == 1)
11 return false;
12 if (n == 2)
13 return true;
14 int t = (int)sqrt(n);
15 for (int i = 3; i <= t; i += 2)
16 if (n % i == 0)
17 return false;
18 return true;
19 }
20
21 void generatePalindrome(int x[], int l, int r)
22 {
23 if (l < 1)
24 return;
25
26 for (int i = 0; i < 10; i++)
27 {
28 x[l] = x[r] = i;
29
30 //=================
31 int n0 = 0, n1 = 0, t;
32
33 if (x[l] != 0 && x[r] % 2 != 0)
34 {
35 t = 1;
36 for (int k = r; k >= l; k--)
37 n0 += x[k] * t, t *= 10;
38
39 t = 1;
40 for (int k = r; k >= l; k--)
41 {
42 n1 += x[k] * t, t *= 10;
43 if (k == 4)
44 n1 += x[k] * t, t *= 10;
45 }
46
47 if (isPrime(n0)) ansNum[ansCnt++] = n0;
48 if (isPrime(n1)) ansNum[ansCnt++] = n1;
49 }
50
51 generatePalindrome(x, l - 1, r + 1);
52 }
53 }
54
55 int main()
56 {
57 freopen("pprime.in", "r", stdin);
58 freopen("pprime.out", "w", stdout);
59
60 int s, t, x[10];
61
62 cin >> s >> t;
63
64 //--------
65 //12345678
66 generatePalindrome(x, 4, 4);
67
68 sort(ansNum, ansNum + ansCnt);
69 for (int i = 0; i < ansCnt; i++)
70 {
71 if (ansNum[i] < s)
72 continue;
73 if (ansNum[i] > t)
74 break;
75 cout << ansNum[i] << endl;
76 }
77
78 return 0;
79 }
80