【USACO 1.5】Prime Palindromes

 /*
TASK: pprime
LANG: C++
SOLVE: 枚举数的长度,dfs出对称的数,判断是否在范围内,是否是素数
原来想着枚举每个范围里的数,但是显然超时,范围最大是10^9。
对称的数只有9*2+9*9*2+9*9*9*2+9*9*9*9*2个,再加上几个九位数的。
共一万多个。
n=10000
复杂度就是O(根号n)。
*/
#include<cstdio>
#include<cstring>
int l,r,ans;
bool is_prime(int x){
for(int i=;i<=x/i;i++)
if(x%i==)return ;
return ;
}
void dfs(char* s,int d,int len){
if(d==(len+)/){
int x;
sscanf(s,"%d",&x);
if(x>=l&&x<=r&&is_prime(x))
printf("%d\n",x);
return;
}
for(int i=(d==);i<=;i++){
s[d]=s[len--d]=i+'';
dfs(s,d+,len);
}
}
void solve(){
char s[];
for(int len=;len<;len++){
memset(s,,sizeof s);
dfs(s,,len);
}
}
int main(){
freopen("pprime.in","r",stdin);
freopen("pprime.out","w",stdout);
scanf("%d%d",&l,&r);
solve();
return ;
}
  
上一篇:Wormholes 分类: POJ 2015-07-14 20:21 21人阅读 评论(0) 收藏


下一篇:让你的sublime text写C代码 (sublime text 2 配置构建C开发环境)