题解 P1217 【[USACO1.5]回文质数 Prime Palindromes】

这道题目让我意识到了卡常的重要性 [直接暴力枚举](https://www.luogu.org/record/show?rid=13093329) ``` #include<bits/stdc++.h> using namespace std; int p[10000000]; int top=1; bool vis[100000000]; inline void prime(register int a,register int b) { for(register int i=2;i<=b;i++) { if(vis[i]==0) { if(i>=a)p[top]=i,top++; for(register int o=i;o<=b;o+=i)vis[o]=1; } } } inline int check(register int k) { register string s; stringstream stream; stream<<k; stream>>s; register int l=s.length(); register int flag=1; for(register int i=0;i<l/2;i++) if(s[i]!=s[l-i-1]) { flag=0; break; } return flag; } int main() { int a,b; cin>>a>>b; prime(a,b); for(register int i=1;i<top;i++) { if(check(p[i])) { printf("%d\n",p[i]); } } } ``` 最后一个点十一秒才出 于是仔细观察代码， 1. i++改为++i 1. o2o3优化 1. register 1. inline 1. printf（） 1. std:: 1. break剪枝 1. 位运算 1. 找到潜藏规律100000000里的最后一个回文质数是9989899 1. 质数筛法优化 于是 ``` #pragma GCC optimize(3) #pragma GCC optimize(2) #include<bits/stdc++.h> int p[10000000]; int top=1; char vis[100000005]; inline void prime(register int a,register int b) { for(register int i=2;i<=b;++i) { if(vis[i]!='1') { if(i>=a)p[top]=i,++top; for(register int o=i;o<=b;o+=(i<<2)) { vis[o]='1'; vis[o+i]='1'; vis[o+(i<<1)]='1'; vis[o+(i<<1)+i]='1'; } } } } inline int check(register int k) { register std:: string s; register std:: stringstream stream; stream<<k; stream>>s; register int l=s.length(); register int flag=1; for(register int i=0;i<l/2;++i) if(s[i]!=s[l-i-1]) { flag=0; break; } return flag; } int main() { register int a,b; std:: cin>>a>>b; if(b==100000000)b=9989899; prime(a,b); register int topp=top; for(register int i=1;i<topp;++i) { if(check(p[i])) { printf("%d\n",p[i]); if(p[i]==9989899)break; } } } ``` [AC](https://www.luogu.org/record/show?rid=13095185) 求过