学步园

因为151既是一个质数又是一个回文数(从左到右和从右到左是看一样的)，所以 151 是回文质数。
写一个程序来找出范围[a,b](5 <= a < b <= 100,000,000)( 一亿)间的所有回文质数;

一开始我就想着先找质数，然后判断回文。但10^8 次，找质数的时间就已经超了。

其实可以判断是否为回文数，然后再判断是否是质数。因为10^8次方里面的回文数在10^4左右，然后在判断是否为质数。

其次，在判断是否为质数的时候，可以先预处理出10^4次方里面的质数，然后用这个来筛选质数。

======================================================================================

其实还有个优化，是提交了之后看分析得的。对于所有的偶数位长度的回文数，都是11的倍数，所以偶数位可以直接不用考虑了，除了11以外。

/*
ID: wuqi9395@126.com
PROG: pprime
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 10010
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
#define For(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
using namespace std;
int is[maxn], pri[maxn], ans = 0;
void get_prime() {
    for (int i = 2; i <= 10000; i++) if (!is[i]) {
        pri[ans++] = i;
        for (int j = i * i; j <= 10000; j += i) is[j] = 1;
    }
}
int a, b, na, nb;
void get_number(int x, int &t) {
    while(x) {
        t++;
        x /= 10;
    }
}
bool check(int x) {
    int p = sqrt(x + 0.5);
    p = lower_bound(pri, pri + ans, p) - pri;
    for (int i = 0; i <= p; i++) if (x % pri[i] == 0) return false;
    return true;
}
void gao(int dig) {
    int x = (dig + 1) / 2;
    int num = 0;
    if (x == 1) {
        for (int i = 1; i <= 9; i += 2) {
            if (dig == 1) num = i;
            else num = i * 10 + i;
            if (check(num) && num >= a && num <= b) printf("%d\n", num);
        }
    }
    if (x == 2) {
        for (int i = 1; i <= 9; i += 2) {
            for (int j = 0; j <= 9; j++) {
                if (dig == 3) num = i * 100 + j * 10 + i;
                else num = i * 1000 + j * 100 + j * 10 + i;
                if (check(num) && num >= a && num <= b) printf("%d\n", num);
            }
        }
    }
    if (x == 3) {
        for (int i = 1; i <= 9; i += 2) {
            for (int j = 0; j <= 9; j++) {
                for (int k = 0; k <= 9; k++) {
                    if (dig == 5) num = i * 10000 + j * 1000 + k * 100 + j * 10 + i;
                    else num = i * 100000 + j * 10000 + k * 1000 + k * 100 + j * 10 + i;
                    if (check(num) && num >= a && num <= b) printf("%d\n", num);
                }
            }
        }
    }
    if (x == 4) {
        for (int i = 1; i <= 9; i += 2) {
            for (int j = 0; j <= 9; j++) {
                for (int k = 0; k <= 9; k++) {
                    for (int l = 0; l <= 9; l++) {
                        if (dig == 7) num = i * 1000000 + j * 100000 + k * 10000 + l * 1000 + k * 100 + j * 10 + i;
                        else num = i * 10000000 + j * 1000000 + k * 100000 + l * 10000 + l * 1000 + k * 100 + j * 10 + i;
                        if (check(num) && num >= a && num <= b) printf("%d\n", num);
                    }
                }
            }
        }
    }
}
int main ()
{
    freopen ("pprime.in", "r", stdin);
    freopen ("pprime.out", "w", stdout);
    get_prime();
    scanf("%d%d", &a, &b);
    get_number(a, na);
    get_number(b, nb);
    while(na <= nb) {
        gao(na);
        na++;
    }
    return 0;
}