C++ 素数判断程序实现：判断两个数是否同时为素数

好的，这是一个经典的编程问题。我们来编写一个C++程序，判断两个数是否都是素数。 ## 🔍 问题分析 我们需要： 1. 输入两个整数 a 和 b 2. 分别判断它们是否是素数 3. 如果**都是素数**，输出 "yes" 4. 否则输出 "no" ## ✅ 素数判断函数 **素数**的定义是：一个大于1的自然数，除了1和它自身以外，不能被其他自然数整除。 ### 🔧 核心判断逻辑 - 如果数字小于等于1，不是素数 - 如果数字等于2，是素数（最小的素数） - 如果数字是偶数且大于2，不是素数 - 从3开始，检查到 sqrt(n) 即可，步长为2（只检查奇数因子） 这种判断方法效率较高，时间复杂度为 O(√n)。 ## 💻 C++ 实现代码 ```cpp #include <iostream> #include <cmath> using namespace std; // 判断一个数是否为素数的函数 bool isPrime(int n) { // 小于等于1不是素数 if (n <= 1) return false; // 2是素数 if (n == 2) return true; // 偶数且大于2不是素数 if (n % 2 == 0) return false; // 检查奇数因子，只需检查到 sqrt(n) int limit = sqrt(n); for (int i = 3; i <= limit; i += 2) { if (n % i == 0) return false; } return true; } int main() { int a, b; // 输入两个数 cin >> a >> b; // 判断并输出结果 if (isPrime(a) && isPrime(b)) { cout << "yes" << endl; } else { cout << "no" << endl; } return 0; } ``` ## 📘 代码说明 ### 函数 `isPrime` 详解 | 条件 | 返回值 | 原因 | |------|--------|------| | `n <= 1` | false | 素数必须大于1 | | `n == 2` | true | 2是唯一的偶数素数 | | `n % 2 == 0` | false | 排除其他偶数 | | 循环检查到 `sqrt(n)` | 根据情况 | 若整除则非素数 | ### 🔑 关键优化点 - **只检查到 sqrt(n)**：如果 n 有因子，必定有一个 ≤ sqrt(n) - **步长为2**：跳过所有偶数，减少一半计算量 - **先排除偶数和小于等于1的情况**：避免不必要的循环 ## 🎯 开发建议 1. **数据类型选择**：如果数值范围较大（超过 int 范围），建议使用 `long long` 类型 2. **输入验证**：可以添加对非法输入的检查（如非数字字符） 3. **性能优化**：对于多次判断素数的场景，可以使用**埃拉托色尼筛法**预处理 4. **边界测试**：测试特殊值如 0、1、2、负数的处理逻辑 ### 📋 常见陷阱 - 忘记处理 `n <= 1` 的情况 - 循环范围写成 `i <= n` 导致超时 - 忽略 `sqrt` 需要 `cmath` 头文件 ## 🔄 扩展功能建议 如需处理更大的数据量或多次查询，可以考虑： - 实现 **素数筛法**（Sieve of Eratosthenes） - 添加 **质因数分解** 功能 - 使用 **Miller-Rabin** 素性测试进行大规模数判断 ######[AI写代码神器 | 828点数解答 | 2026-07-17 21:17:24]