本文主要是介绍USACO Section 1.5 Prime Palindromes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
输入a和b 求 a和b之间所有既是素数同时又有回文性质的数 从小到大输出
思路：
如果枚举a到b之间所有的数再判断素数和回文那么复杂度会比O(n)还大 本题O(n)都会跪
因此思路转到能否 先得到所有素数再判断回文 或者 先得到所有回文的数在判断素数
本题我的做法是后者 说下原因
本题b最大为10^8 因此构造回文的数字可以枚举1~10000中的数字再对数字翻折即可
因为翻折方法有2种 所以构造出的回文的数字最多也就20000个 然后在判断20000个数是否为素数
这是一个非常小的计算量！！
2种翻折的方法也不难想 如果枚举的4位数字为abcd 则翻折后可以是 abcddcba 或者 abcdcba
在此基础上判断素数可以用暴力的方法（大概吧…我没试过…）
我的做法是打sqrt(n)的素数表 再用素数表判断
代码：
/*
ID: housera1
PROG: pprime
LANG: C++
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;int x[10],p[10010],flag[10010],ans[20010];
int cnt,tot,tmp1,tmp2;void init()
{int i,j;for(i=2;i<10000;i++){if(!flag[i]) p[cnt++]=i;for(j=0;j<cnt&&p[j]*i<10000;j++){flag[i*p[j]]=1;if(i%p[j]==0) break;}}
}void getnum(int f)
{int i,j,up,dn;for(i=3,j=4;f;i--,j++,f/=10) x[i]=x[j]=f%10;for(up=0,dn=7;!x[up];up++,dn--);for(tmp1=0,tmp2=0,i=up;i<=dn;i++){tmp1=tmp1*10+x[i];if(i!=4) tmp2=tmp2*10+x[i];}
}bool yes(int y)
{int i,j=lower_bound(p,p+cnt,sqrt(y))-p;for(i=0;i<=j;i++) if(y%p[i]==0) return false;return true;
}int main(){int Debug=0;if(!Debug){freopen("pprime.in","r",stdin);freopen("pprime.out","w",stdout);}int i,a,b;init();scanf("%d%d",&a,&b);for(i=1;i<10000;i++){getnum(i);if(tmp1>=a&&tmp1<=b&&yes(tmp1)) ans[tot++]=tmp1;if(tmp2>=a&&tmp2<=b&&yes(tmp2)) ans[tot++]=tmp2;}sort(ans,ans+tot);for(i=0;i<tot;i++) printf("%d\n",ans[i]);return 0;
}
这篇关于USACO Section 1.5 Prime Palindromes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
