唤我沈七就行嘿嘿。
大一软件工程在读。
菜鸡蒟蒻想在博客中记录一些算法学习的心得体会，会持续更新C/C++方面的题解，方便理清思路和日后复习。如果还能结识一起敲代码的小伙伴的话就更好啦嘿嘿，因为笔者实在是太弱了，肯定免不了错误百出。
欢迎批评指正，期待共同成长！
题目链接
题目描述
因为 151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151 是回文质数。
写一个程序来找出范围 [a,b](5≤a<b≤100,000,000) 一亿)间的所有回文质数。
输入样例
输入
5 500
输出
5 7 11 101 131 151 181 191 313 353 373 383
题解部分
涉及算法：数论、线性筛、回文数
针对线性筛我已经在上篇博客进行了详细讲解，建议读者在阅读下文题解之前在复习一遍。
算法模板：数论之质数全家桶（内含埃氏筛法，欧拉线性筛法模板）
思路
1.题目的亿级别的数据,说明暴力枚举，即试除法求素数，必然超时。这时我们的线性筛模板就派上了用场。
#define N 100000010 int cnt;//计数 int p[N];//存放质数 bool st[N];//用来筛掉合数，也可以用整型数组代替，1相当于true，0相当false void get_prime(int n) { for(int i = 2; i <= n; i++) { if(!st[i]) p[cnt++] = i; for(int j = 0; p[j] <= n / i; j++) { //对于任意一个合数n，假设pj为n最小质因子，当i<=n/p[j]时，一定会被筛掉 //因为i枚举到n之前,一定会枚举到n/p[j],而当n/p[j]不就是合数n的因子， //所以x一定会被在i<=n/p[j]时被筛除。 st[p[j]*i] = true; if(i % p[j] == 0) break; } } }
2 . 那回文数如何判断呢？
既然是回文数即正着读和倒着读一样，
那我们就把要判断的数倒置之后再和倒置之前的数判断是否相等，
若相等即为回文数。
int a,b,c; while(a1) { b=a%10; c=c*10+b; a/=10; } if(c==p[i]) printf("%d\n",p[i]);
3 .我们将前面提到的两点进行合并，即在指定区间用线性筛之后将质数存贮起来，在判断是否为回文数，整理成程序提交后，发现还是TLE（超时）了一个测试点。
要知道我们使用可是最快的线性筛，那怎么样进一步优化呢？
我们又需要用到一个新的知识点，
除了11以外，一个数的位数是偶数的话，不可能为回文数素数。
证明 如果一个回文素数的位数是偶数，则它的奇数位上的数字和与偶数位上的数字和必然相等； 根据数的整除性理论，容易判断这样的数肯定能被11整除，所以它就不可能是素数
有了这一结论，事情就变的简单了，我们只需要在判断小于8位数的数是否为素数即可。
做法是需要在线性筛判断上加一个特判。
void get_prime(int n) { for( int i=2;i<=n;i++) { if(i>10000000) continue; else { if(!a[i])p[t++]=i; for(int j=0;p[j]<=n/i;j++) { a[i*p[j]]=true; if(i%p[j]==0)break; } } } }
ok核心部分已经讲解完毕，下面奉上完整代码。
完整代码
C++版
#include<bits/stdc++.h> #define N 100000010 using namespace std; int p[N],t; bool st[N]; void get_prime(int n) { for( int i=2;i<=n;i++) { if(i>10000000) continue; else { if(!st[i])p[t++]=i; for(int j=0;p[j]<=n/i;j++) { st[i*p[j]]=true; if(i%p[j]==0)break; } } } } int main() { int i,j; int m,n; int a,b,c=0; scanf("%d%d",&m,&n); get_prime(n); for(i=0;i<t;i++) { a=p[i]; if(a<m) continue; c=0; while(a) { b=a%10; c=c*10+b; a/=10; } if(c==p[i]) printf("%d\n",p[i]); } return 0; }
C语言版
#include<stdio.h> #define N 100000010 int p[N],t; int st[N]; void get_prime(int n) { for( int i=2;i<=n;i++) { if(i>10000000) continue; else { if(!st[i])p[t++]=i; for(int j=0;p[j]<=n/i;j++) { st[i*p[j]]=1; if(i%p[j]==0)break; } } } } int main() { int i,j; int m,n; int a,b,c=0; scanf("%d%d",&m,&n); get_prime(n); for(i=0;i<t;i++) { a=p[i]; if(a<m) continue; c=0; while(a) { b=a%10; c=c*10+b; a/=10; } if(c==p[i]) printf("%d\n",p[i]); } return 0; }
未完待续
孩子测试了一下C语言版的，发现将bool 型数组转换为int 数组来标记合数的话，在最后一个测试点内存会爆掉。
如果读者C语言版的代码有更好的解决方案的话，欢迎评论区讨论。
肯定回关哦，没有什么粉丝，只有学习伙伴，要是能有幸和你一起进步那就太棒啦.
参考文章
https://blog.csdn.net/m0_66139206/article/details/
