USACO 1.5 Prime Palindromes(列挙)
20929 ワード
素数を選別したかったのですが...渡してみると複雑さが高すぎて...耻ずかしいことにhintを见て、それから各种forは一人一人を列挙しました...
1 /*
2 ID: cuizhe
3 LANG: C++
4 TASK: pprime
5 */
6 #include <cstdio>
7 #include <cstring>
8 #include <cmath>
9 #include <algorithm>
10 using namespace std;
11 #define N 1000001
12 bool p[N];
13 int prim[100000],num;
14 int judge(int x)
15 {
16 int i;
17 for(i = 1;i <= num-1;i ++)
18 {
19 if(prim[i] > x)
20 break;
21 if(x%prim[i] == 0)
22 return 0;
23 }
24 return 1;
25 }
26 int main()
27 {
28 int i,j,k,u;
29 long long t,a,b;
30 freopen("pprime.in","r",stdin);
31 freopen("pprime.out","w",stdout);
32 scanf("%lld%lld",&a,&b);
33 for(i = 2; i <= N; i ++)
34 {
35 if(!p[i])
36 {
37 for(j = i+i; j <= N; j += i)
38 {
39 p[j] = 1;
40 }
41 }
42 }
43 num = 1;
44 for(i = 2;i <= N;i ++)
45 {
46 if(!p[i])
47 prim[num++] = i;
48 }
49 for(i = 1;i <= 9;i += 2)//
50 {
51 if(!p[i]&&i >= a&&i <= b)
52 printf("%d
",i);
53 }
54 for(i = 1;i <= 9;i += 2)//
55 {
56 if(!p[i*10+i]&&i*10+i>=a&&i*10+i<=b)
57 printf("%d
",i*10+i);
58 }
59 for(i = 1;i <= 9;i += 2)//
60 {
61 for(j = 0;j <= 9;j ++)
62 {
63 if(!p[i*100+j*10+i]&&i*100+j*10+i>=a&&i*100+j*10+i<=b)
64 printf("%d
",i*100+j*10+i);
65 }
66 }
67 for(i = 1;i <= 9;i += 2)//
68 {
69 for(j = 0;j <= 9;j ++)
70 {
71 if(!p[i*1000+j*100+10*j+i]&&i*1000+j*100+10*j+i>=a&&i*1000+j*100+10*j+i<=b)
72 printf("%d
",i*100+j*100+10*j+i);
73 }
74 }
75 for(i = 1;i <= 9;i += 2)//
76 {
77 for(j = 0;j <= 9;j ++)
78 {
79 for(k = 0;k <= 9;k ++)
80 {
81 t = i*10000+i+1000*j+10*j+k*100;
82 if(!p[t]&&t>=a&&t<=b)
83 printf("%lld
",t);
84 }
85 }
86 }
87 for(i = 1;i <= 9;i += 2)//
88 {
89 for(j = 0;j <= 9;j ++)
90 {
91 for(k = 0;k <= 9;k ++)
92 {
93 t = i*100000+i+10000*j+10*j+k*1000+k*100;
94 if(!p[t]&&t >= a&&t <= b)
95 printf("%lld
",t);
96 }
97 }
98 }
99 for(i = 1;i <= 9;i += 2)//
100 {
101 for(j = 0;j <= 9;j ++)
102 {
103 for(k = 0;k <= 9;k ++)
104 {
105 for(u = 0;u <= 9;u ++)
106 {
107 t = 1000000*i+i+100000*j+10*j+10000*k+k*100+1000*u;
108 if(judge(t)&&t >= a&&t <= b)
109 printf("%lld
",t);
110 }
111 }
112 }
113 }
114 for(i = 1;i <= 9;i += 2)//
115 {
116 for(j = 0;j <= 9;j ++)
117 {
118 for(k = 0;k <= 9;k ++)
119 {
120 for(u = 0;u <= 9;u ++)
121 {
122 t = 10000000*i+i+1000000*j+10*j+100000*k+k*100+10000*u+1000*u;
123 if(judge(t)&&t >= a&&t <= b)
124 printf("%lld
",t);
125 }
126 }
127 }
128 }
129 return 0;
130 }