C++ 实现：快速判断正整数是否为质数，附代码详解与复杂度分析

```cpp #include <iostream> int main() { int n; std::cin >> n; // 如果 n 小于等于 1，它不是质数 if (n <= 1) { std::cout << (n > 1? "Yes" : 0) << std::endl; return 0; } // 从 2 开始检查约数 for (int i = 2; i * i <= n; ++i) { if (n % i == 0) { // 找到第二小的约数 std::cout << i << std::endl; return 0; } } // 如果没有找到除 1 和自身之外的约数，n 是质数 std::cout << "Yes" << std::endl; return 0; } ``` 代码解释 1. 输入处理：使用 `std::cin` 读取用户输入的正整数 `n`。 2. 特殊情况处理：如果 `n` 小于等于 1，它不是质数，根据题目要求输出结果。 3. 检查约数：从 2 开始遍历到 `sqrt(n)`，如果 `n` 能被 `i` 整除，说明 `n` 不是质数，输出 `i` 作为第二小的约数。 4. 质数判断：如果没有找到除 1 和自身之外的约数，说明 `n` 是质数，输出 `Yes`。 复杂度分析 - 时间复杂度：$O(\sqrt{n})$，因为只需要遍历到 `sqrt(n)`。 - 空间复杂度：$O(1)$，只使用了常数级的额外空间。 ######[AI问答 | 402点数解答 | 2025-11-08 21:02:42]