如何高效生成指定范围内的素数回文数？规避全量遍历方案

问题背景 #

我查阅过该问题的现有解决方案，但均为全量遍历加检查函数的方式，效率无法满足需求。目前正在编写C++程序，旨在高效生成指定整数范围内的所有素数回文数。针对素数检测部分，已通过排除2和3的倍数优化了素性检测函数，同时希望获得更多优化建议。核心需求是：无需采用逐次递增整数并检测回文的传统全量遍历方式，快速生成回文数。曾尝试通过递增数字中间位再扩展外层的方式实现，但因位数变化的问题未能完成算法。

现有代码 #

素性检测函数

bool CheckPrime(int n){
    switch (n) {
    case 1: return false;  break;
    case 2: return true;  break;
    case 3: return true;  break;
    default: break;
    }
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
    for (int i = 5; i * i <= n; i = i + 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

回文检测及主函数

bool CheckPalindrome (int n) {
    string temp = to_string(n);
    reverse(temp.begin(), temp.end());
    if (temp.compare((to_string(n))) == 0) {
        return true;
    }
    else {
        return false;
    }
}


int main() {
int L, R; cin >> L >> R;
vector <int> Palindromes;
for (int i = L; i <= R; i++) {
    if (CheckPalindrome(i)) {
        Palindromes.push_back(i);
    }
}
}

高效生成回文数的实现思路 #

直接生成回文数而非遍历所有数字检测，能大幅减少需要处理的数的数量。可以按数字位数分类处理，分别生成奇数位和偶数位回文：

1. 分位数生成回文

• 奇数位回文：比如生成3位回文，取包含中间位的前半部分数字，反转前半部分的前k-1位（k为前半部分长度），拼接到原数字后。例如：基础数12 → 反转前1位得1 → 拼接成121。
• 偶数位回文：比如生成4位回文，取前半部分数字，直接反转后拼接到原数字后。例如：基础数12 → 反转得21 → 拼接成1221。

2. 处理位数变化

先计算目标范围[L,R]对应的最小位数和最大位数，遍历每一种位数生成对应回文数，再过滤出在[L,R]内的数，最后做素性检测。

素性检测的优化建议 #

1. 提前排除偶数位回文（除11外）：所有大于11的偶数位回文数都是11的倍数，不可能是素数，生成时直接跳过素性检测，节省大量时间。
2. 避免整数溢出：素性检测循环中i*i可能超出int范围，将i改为long long，或者用(long long)i * i <= n判断：

   for (long long i = 5; i * i <= n; i += 6) {
       if (n % i == 0 || n % (i + 2) == 0) {
           return false;
       }
   }
   

3. 缓存小素数：预先用筛法生成小素数表，先让目标数除以这些小素数，再进入循环，减少循环次数。

完整实现示例 #

整合上述思路的主函数示例，直接生成回文数再检测素数：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

bool CheckPrime(int n){
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (long long i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

vector<int> generatePalindromes(int len, int L, int R) {
    vector<int> res;
    if (len == 1) {
        for (int i = 1; i <= 9; ++i) {
            if (i >= L && i <= R) res.push_back(i);
        }
        return res;
    }
    int half_len = len / 2;
    int start = pow(10, half_len - 1);
    int end = pow(10, half_len) - 1;

    for (int base = start; base <= end; ++base) {
        string base_str = to_string(base);
        string palindrome_str;
        if (len % 2 == 0) {
            palindrome_str = base_str + string(base_str.rbegin(), base_str.rend());
        } else {
            palindrome_str = base_str + string(base_str.rbegin() + 1, base_str.rend());
        }
        int palindrome = stoi(palindrome_str);
        if (palindrome > R) break;
        if (palindrome >= L) {
            res.push_back(palindrome);
        }
    }
    return res;
}

int main() {
    int L, R;
    cin >> L >> R;

    int min_len = to_string(L).size();
    int max_len = to_string(R).size();

    vector<int> primePalindromes;

    for (int len = min_len; len <= max_len; ++len) {
        vector<int> pals = generatePalindromes(len, L, R);
        for (int pal : pals) {
            if (len % 2 == 0 && pal != 11) continue;
            if (CheckPrime(pal)) {
                primePalindromes.push_back(pal);
            }
        }
    }

    for (int num : primePalindromes) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

内容的提问来源于stack exchange，提问作者Hudson