【深基4.例14】[USACO1.5] 回文质数 Prime Palindromes

解题思路

枚举回文数左半部分，分别构造奇数长度与偶数长度回文，筛选区间并排序去重，再试除判断质数。

正确性说明

每个回文数由前半部分唯一确定；1～9999 的半部枚举覆盖一亿以内可能的回文质数。试除排除全部合数。

易错点

不要枚举区间内一亿个整数；11 也需要保留；逐行升序输出。

复杂度

候选数 K≤19998，时间 O(K√B+K log K)，空间 O(K)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b;
    cin >> a >> b;
    vector<int> v;
    for (int h = 1; h <= 9999; h++) {
        for (int odd = 0; odd <= 1; odd++) {
            int x = h, t = odd ? h / 10 : h;
            while (t) {
                x = x * 10 + t % 10;
                t /= 10;
            }
            if (x >= a && x <= b)
                v.push_back(x);
        }
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int x : v) {
        bool ok = x >= 2;
        for (int k = 2; k * k <= x; k++)
            if (x % k == 0) {
                ok = false;
                break;
            }
        if (ok)
            cout << x << "\n";
    }
    return 0;
}