HDU 1431 素數回文：生成回文數並判斷素性

題目大意

求區間 [a, b]（b ≤ 1e8）內所有既是素數又是回文的數。

生成回文數而非篩素數

直接篩 1e8 內素數記憶體過大。觀察：回文數極少。生成所有 ≤ 1e8 的回文數（約 2萬個），再逐個判斷素性（試除法至 √n）。

生成方法：枚舉前半部分 1..9999，鏡像構造奇數長度和偶數長度回文數。
例如 123 → 12321 (奇) 和 123321 (偶)。

參考代碼 (C++)

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

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; ++i)
        if (x % i == 0) return false;
    return true;
}

vector palPrimes;

void gen() {
    palPrimes = {2,3,5,7,11}; // 手動添加小數
    for (int half = 1; half <= 9999; ++half) {
        string s = to_string(half);
        string rev = s; reverse(rev.begin(), rev.end());
        // 奇數長度
        int odd = stoi(s + rev.substr(1));
        if (odd <= 100000000 && isPrime(odd)) palPrimes.push_back(odd);
        // 偶數長度
        int even = stoi(s + rev);
        if (even <= 100000000 && isPrime(even)) palPrimes.push_back(even);
    }
    sort(palPrimes.begin(), palPrimes.end());
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    gen();
    int a, b;
    while (cin >> a >> b) {
        for (int p : palPrimes)
            if (p >= a && p <= b) cout << p << '\n';
        cout << '\n';
    }
    return 0;
}

複雜度

生成約 2萬個回文數，每個試除 O(√n) ≈ 1e4，總預處理約 2e8 操作，離線預計算一次即可。查詢 O(log N) 二分輸出。