C++实现：输入正整数判断质数，非质数输出第二小约数（复杂度O(√n)）

```cpp #include <iostream> #include <cmath> using namespace std; int main() { int n; cin >> n; if (n <= 1) { cout << "No" << endl; return 0; } for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { cout << i << endl; return 0; } } cout << "Yes" << endl; return 0; } ``` 代码说明： 1. 输入正整数n 2. 处理n≤1的情况，直接输出"No" 3. 从2到√n遍历，找到第一个能整除n的约数i 4. 找到约数i时输出i（第二小的约数） 5. 没有找到约数时输出"Yes"（质数） 时间复杂度：O(√n) ######[AI问答 | 197点数解答 | 2025-11-07 21:14:46]