【深基7.习5】[USACO1.5] 回文质数 Prime Palindromes

解题思路

枚举回文数的左半部分，把左半部分倒序拼接得到奇数位回文和偶数位回文。筛选范围后排序、去重，再逐个试除判断质数。

正确性说明

任意回文数都由前一半（奇数长度时含中位）唯一确定。枚举 1～9999 足以覆盖上界一亿以内所有可能的回文质数；一亿本身不是回文。试除判定后只输出区间内的质数。

易错点

不要逐个枚举一亿个整数；偶数长度回文也生成，避免漏掉 11；排序后输出。

复杂度

设生成候选数为 K（不超过 19998），上界为 B，时间 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;
}