首页 > 代码库 > Prime Palindromes
Prime Palindromes
题目大意:求出区间[a,b]之间的回文质数。 a<=b<=10^8;
解题过程：
1.先打个素数表，新学了个 欧拉筛法，是对普通筛法的改进。普通筛法是每找到一个素数，就把它的所有倍数标记成1，那么对于一个合数，它会被它的所有质因数标记一次。那么就浪费了时间（复杂度O(NloglogN)）。欧拉筛法的复杂度可以降到O(N)，
它的优化在于 找到一个质数的时候，把所有是它的质数倍的数标记成1（搜一遍已经找到的质数），如果某一个质数是它的约数，那么break；见代码：
1 void generate_prime() 2 { 3 int c; 4 check[1]=1; 5 for (int i=2;i<=10000;i++) 6 { 7 if (!check[i]) 8 prime[++cnt]=i; 9 for (int j=1;j<=cnt;j++)10 {11 c=i*prime[j];12 if (c>10000)13 break;14 check[c]=true;15 if (i % prime[j]==0)16 break;17 }18 }19 }
2.接下来是如何产生回文数，首先0到9必定是，先放到表中。需要分情况考虑：
A.回文数的位数 是偶数。 那么从1到10000枚举回文数的一半，如何产生另一半。
B.回文数的位数 是奇数， 那么先枚举最中间的那个数，然后枚举左边一半，从1到1000；
3.最后写个判断质数的函数，把所有符合要求的放入一个表中，排个序输出即可。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。