补题：回文质数

本质上这题还是有关筛素数，但是增多了一些细节，还是值得注意和思考一下的

• 题目大意为在一个有限范围内求出[a,b]内即是回文数又是质数的数并打出

• ---

  一开始是也是想先把质数筛出来，出现的问题主要是回文数的判断这里浪费的许多空间以至于MLE了过不去，用的to_string加reverse加string大数组，再加上对数据的范围不熟悉(题目的数据范围是一亿)，以至于用龙long long浪费了大量的空间，根本过不去。
• 其实回文数的判断只需要这样就行了，基本没花什么空间

  1 bool judge(int n) {
  2     int num = n, m = 0;
  3     while (n) {
  4         m = m * 10 + n % 10;
  5         n /= 10;
  6     }
  7     if (m == num)return true;
  8     return false;
  9 }

  之后就改为了将范围内的所有素数筛出来后判断就可以了，下面是ac代码

•  1 #include<iostream>
   2 #include<cstring>
   3 #include<algorithm>
   4 #include<cmath>
   5 #include<string>
   6 using namespace std;
   7 
   8 const int N = 1e7;
   9 
  10 int prime[N], cnt, ans[N], num;
  11 bool st[N];
  12 
  13 void find_prime(int b) {
  14     if (b > 1e7)b = 9999999;
  15 
  16     for (int i = 2; i <= b; i++) {
  17 
  18         if (!st[i])prime[cnt++] = i;
  19 
  20         for (int j = 0; prime[j] <= b / i; j++) {
  21             st[prime[j] * i] = true;
  22             if (i % prime[j] == 0)break;
  23         }
  24     }
  25 }
  26 
  27 bool judge(int n) {
  28     int num = n, m = 0;
  29     while (n) {
  30         m = m * 10 + n % 10;
  31         n /= 10;
  32     }
  33     if (m == num)return true;
  34     return false;
  35 }
  36 
  37 int main()
  38 {
  39     int a, b;
  40     cin >> a >> b;
  41     find_prime(b);   
  42     for (int i = cnt - 1; prime[i] >= a; i--) {
  43         if (judge(prime[i]))ans[num++] = prime[i];
  44     }
  45     for (int i = num - 1; i >= 0; i--)cout << ans[i] << endl;
  46     return 0;
  47 }

   

• 不过我们可以看到我们间接也学会了如何在任意区间里面筛素数，我们只需要将用传统的素数筛法将大边界以内的素数筛出来再对要用的数据范围加以限制就好了。