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\n",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