C++素数判定程序实现与性能优化详解

好的，这是一个非常经典的编程问题。下面我将为你提供一个高效、清晰的C++解决方案，并附带详细的解释。 ## 💡 解题思路 素数的定义是：**一个大于1的自然数，除了1和它本身以外不再有其他因数**。我们只需要检查从2到 `sqrt(n)` 之间是否有任何数能整除 `n`。如果找到了，就不是素数；否则，就是素数。 > **优化点**：检查到 `sqrt(n)` 即可，因为如果 `n` 有一个大于 `sqrt(n)` 的因子，那么它必然有一个小于 `sqrt(n)` 的因子。这样可以大幅减少循环次数，尤其对于大数来说性能提升明显。 ## 🖥️ C++代码实现 ```cpp #include <iostream> #include <cmath> // 用于 sqrt 函数 using namespace std; bool isPrime(int n) { // 素数必须大于1，且题目保证n>=2 if (n < 2) return false; // 2是素数 if (n == 2) return true; // 偶数除了2都不是素数 if (n % 2 == 0) return false; // 检查奇数因子，范围从3到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 n; cin >> n; if (isPrime(n)) { cout << "yes" << endl; } else { cout << "no" << endl; } return 0; } ``` ## 📋 代码详解 1. **`#include <cmath>`**：需要用到 `sqrt` 函数计算平方根。 2. **`isPrime` 函数**： - 先处理特殊值：`n < 2` 时返回 `false`（虽然题目保证 `n>=2`，但加此判断更安全）。 - 处理 `n == 2` 的情况，2 是素数。 - 如果 `n` 是偶数且大于2，则一定不是素数（直接返回 `false`）。 - 然后从 `3` 开始，**步长为2**（只检查奇数），直到 `sqrt(n)`，寻找因子。 3. **主函数**： - 读取整数 `n`。 - 调用 `isPrime` 函数判断，并输出相应的结果。 ## ⏱️ 复杂度分析 - **时间复杂度**：O(√n)。因为最多检查 √n 个数字（实际上只检查奇数，约 √n/2 次）。 - **空间复杂度**：O(1)。只使用了常数个额外变量。 ## 🧪 测试用例 | 输入 | 输出 | 说明 | |------|------|------| | 2 | yes | 最小的素数 | | 3 | yes | 素数 | | 4 | no | 偶数，非素数 | | 9 | no | 3*3 | | 13 | yes | 素数 | | 97 | yes | 素数 | | 100 | no | 10*10 | ## 🚀 进阶建议 1. **处理大数据**：如果需要多次判断大量数字是否为素数（如1e6次），建议使用**埃拉托色尼筛法（Sieve of Eratosthenes）** 预处理，查询时O(1)。 2. **边界情况**：实际开发中，建议考虑负数、0、1等特殊输入，虽然题目中限制了 `n>=2`。 3. **性能优化**：对于非常大的数（如超过32位整数），可以考虑使用**米勒-拉宾素性测试**（Miller-Rabin primality test），这是一个概率性算法，速度远快于试除法。 4. **常见陷阱**：注意 `sqrt(n)` 的浮点精度问题。对于大整数，使用 `i * i <= n` 作为循环条件可以避免浮点误差，但要注意 `i * i` 可能溢出（对于32位int，n最大约21亿，`i` 最大约46340，`i*i` 不会溢出，但仍建议使用 `long long` 或判断条件）。 ######[AI写代码神器 | 955点数解答 | 2026-07-17 21:15:10]