C++三位数回文质数查找算法及优化实现

好的，这个问题很明确，我们需要找出所有**三位数的回文质数**。 --- ### 🧠 思路分析 三位数范围是 **100 到 999**（实际上三位数最小是100，但100不是质数）。 我们需要同时满足两个条件： 1. **回文数**：百位 = 个位。 2. **质数**：只能被 1 和自身整除。 --- ### 🔍 算法步骤 1. **遍历** 100 到 999 的所有整数 `n`。 2. **判断回文**：对于三位数，只需比较 `百位 == 个位`，即 `n/100 == n%10`。 3. **判断质数**：用一个循环，从 2 到 `sqrt(n)`（或 `n/2`）检查是否能整除。 4. 如果同时满足，则输出。 --- ### 💻 C++ 代码实现 ```cpp #include <iostream> #include <cmath> using namespace std; // 判断一个数是否为质数 bool isPrime(int n) { if (n < 2) return false; if (n == 2) return true; if (n % 2 == 0) return false; // 排除偶数 int limit = sqrt(n); for (int i = 3; i <= limit; i += 2) { if (n % i == 0) return false; } return true; } int main() { for (int num = 100; num <= 999; num++) { // 三位数回文条件：百位 == 个位 if (num / 100 == num % 10) { if (isPrime(num)) { cout << num << endl; } } } return 0; } ``` --- ### 📝 代码解释 - **`isPrime` 函数**： - 排除小于2的数，排除2自身，排除偶数（2除外）。 - 只检查奇数因子，范围到 `sqrt(n)`，提高效率。 - **主循环**： - 从100到999，先判断回文（百位等于个位），再判断质数。 - 满足条件则输出。 --- ### ⚡ 优化建议 - 实际上三位数的回文数只有 **90个**（因为百位从1-9，十位从0-9，百位决定个位），我们可以直接生成这些数，再判断质数，效率更高。例如： ```cpp for (int a = 1; a <= 9; a++) { for (int b = 0; b <= 9; b++) { int num = a * 100 + b * 10 + a; if (isPrime(num)) cout << num << endl; } } ``` 这样无需遍历1000个数，只需90次循环。 --- ### ✅ 运行结果（预期输出） ``` 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929 ``` --- ### 📚 知识点 - **回文数判断**：对于三位数，本质是比较首位和末位。 - **质数判断**：优化点在于只检查到 `sqrt(n)`，并且跳过偶数因子。 - **代码可读性**：将判断逻辑封装成函数，便于复用和测试。 --- ### 💡 开发建议 - 在竞赛或面试中，可以先枚举回文数，再判断质数，减少无用计算。 - 考虑使用 `constexpr` 或宏定义边界，提高可维护性。 - 若需要处理更大规模，可以使用素数筛（如埃拉托斯特尼筛法）预处理质数表。 ######[AI写代码神器 | 846点数解答 | 2026-08-28 20:36:08]