三位数回文质数枚举与优化实现

好的，我们来解决这个“找出所有三位数回文质数”的编程问题。 这是一个非常经典的枚举与数学判断结合的题目。我们将分别解释 **质数** 和 **回文数** 的判断逻辑，然后给出多种语言的实现代码（以 Python 为首选，兼顾 C++ 和 Java）。 ### 🧠 核心思路 1. **范围**：三位数是从 `100` 到 `999`。 2. **条件一：回文数**： - 对于三位数 abc，其百位和个位必须相等，即 `a == c`。 - 例如：101 的百位和个位都是 `1`。 3. **条件二：质数**： - 一个大于1的自然数，除了1和它自身以外，不能被其他自然数整除。 - 常用的判断方法是：从 `2` 遍历到 `sqrt(n)`，检查是否能被整除。 **优化小提示**：由于回文数的判断非常快（只需比较百位和个位），而质数判断相对较慢，因此**先判断是否为回文数，再判断是否为质数**，可以大幅减少质数判断的次数，提高程序效率。 --- ### 🛠️ 代码实现 #### 1. Python 实现 （推荐） ```python import math def is_prime(n): """判断一个数是否为质数""" if n < 2: return False # 只需要检查到 sqrt(n) for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return False return True def is_palindrome_three_digit(n): """判断一个三位数是否为回文数""" # 百位：n // 100 # 个位：n % 10 return n // 100 == n % 10 # 主循环 print("三位数的回文质数有:") for num in range(100, 1000): # 先快速筛选回文 if is_palindrome_three_digit(num): # 再判断质数 if is_prime(num): print(num) ``` **输出结果：** ```text 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929 ``` --- #### 2. C++ 实现 ```cpp #include <iostream> #include <cmath> using namespace std; // 判断质数 bool isPrime(int n) { if (n < 2) return false; for (int i = 2; i <= sqrt(n); ++i) { if (n % i == 0) return false; } return true; } // 判断三位数回文 bool isPalindrome(int n) { // 百位：n / 100，个位：n % 10 return (n / 100) == (n % 10); } int main() { cout << "三位数的回文质数:" << endl; for (int i = 100; i < 1000; ++i) { if (isPalindrome(i) && isPrime(i)) { cout << i << endl; } } return 0; } ``` --- #### 3. Java 实现 ```java public class PalindromicPrimes { // 判断质数 public static boolean isPrime(int n) { if (n < 2) return false; for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) return false; } return true; } // 判断三位数回文 public static boolean isPalindrome(int n) { return (n / 100) == (n % 10); } public static void main(String[] args) { System.out.println("三位数的回文质数:"); for (int i = 100; i < 1000; i++) { if (isPalindrome(i) && isPrime(i)) { System.out.println(i); } } } } ``` --- ### 🚀 进阶优化与深度解读 1. **为何先判断回文？** - 在 100-999 范围内，数字有 900 个。先判断回文，只需比较一次位运算，可以立即排除掉 90% 的数字（只有 90 个回文数），而质数判断需要做多次取模运算。**先易后难**是优化的基本原则。 2. **质数判断的边界** - 使用 `sqrt(n)` 作为循环上限是最高效的。因为如果 `n` 有一个大于 `sqrt(n)` 的因子，那么它必然有一个小于 `sqrt(n)` 的因子。 - **陷阱**：注意循环边界要包含 `sqrt(n)`，即 `i <= sqrt(n)`。 3. **扩展到任意位数** - 如果题目不限定是三位数，而是求 N 位数的回文质数，则需要更复杂的回文生成算法（如镜像构造），而不是直接枚举，因为直接枚举会随着位数增大会非常慢。 4. **常见面试追问** - **Q:** 为什么没有偶数位的回文质数（除了 11）？ - **A:** 因为一个偶数位的回文数，其数字和必然是偶数（例如 11 位对称，偶数位数字对称加起来能被 2 整除），所以能被 11 整除。因此除了 11 本身，没有其他偶数位的回文质数。这可以解释为什么上面代码中 `111` 没有被输出（虽然它是回文，但不是质数）。 ### ✨ 开发建议 1. **模块化**：将 `is_prime` 和 `is_palindrome` 写成独立函数，代码清晰且易于复用。 2. **测试边界**：特别注意 `n=2` 和 `n=1` 的情况。 3. **不要预判结果**：在写代码之前，可以先用数学知识（如偶数位回文质数只有 11）来缩小搜索范围，但作为通用解法，直接枚举是最安全且容易检查的方案。 ######[AI写代码神器 | 1386点数解答 | 2026-06-06 07:30:14]