【USACO 1.5】Prime Palindromes

 1 /*
 2 TASK: pprime
 3 LANG: C++
 4 SOLVE: 枚举数的长度，dfs出对称的数，判断是否在范围内，是否是素数
 5 原来想着枚举每个范围里的数，但是显然超时，范围最大是10^9。
 6 对称的数只有9*2+9*9*2+9*9*9*2+9*9*9*9*2个，再加上几个九位数的。
 7 共一万多个。
 8 n=10000
 9 复杂度就是O(根号n)。
10  */
11 #include<cstdio>
12 #include<cstring>
13 int l,r,ans;
14 bool is_prime(int x){
15     for(int i=2;i<=x/i;i++)
16         if(x%i==0)return 0;
17     return 1;
18 }
19 void dfs(char* s,int d,int len){
20     if(d==(len+1)/2){
21         int x;
22         sscanf(s,"%d",&x);
23         if(x>=l&&x<=r&&is_prime(x))
24             printf("%d
",x);
25         return;
26     }
27     for(int i=(d==0);i<=9;i++){
28         s[d]=s[len-1-d]=i+'0';
29         dfs(s,d+1,len);
30     }
31 }
32 void solve(){
33     char s[12];
34     for(int len=1;len<9;len++){
35         memset(s,0,sizeof s);
36         dfs(s,0,len);
37     }
38 }
39 int main(){
40     freopen("pprime.in","r",stdin);
41     freopen("pprime.out","w",stdout);
42     scanf("%d%d",&l,&r);
43     solve();
44     return 0;
45 }
46