C++ 实现：判断正整数是否为质数并输出对应结果

以下是解决该问题的C++代码： ```cpp #include <iostream> using namespace std; // 该函数用于判断一个数是否为质数，并根据情况输出结果 void checkPrime(int n) { // 质数是大于1的自然数 if (n <= 1) { // 若n小于等于1，从2开始找约数 for (int i = 2; i <= n; i++) { if (n % i == 0) { cout << i << endl; return; } } } // 从2开始遍历到该数的平方根 for (int i = 2; i * i <= n; i++) { if (n % i == 0) { // 若能被整除，说明不是质数，输出第二小的约数 cout << i << endl; return; } } // 若没有找到除1和自身以外的约数，说明是质数 cout << "Yes" << endl; } int main() { int n; // 读取输入的正整数 cin >> n; // 调用函数进行判断 checkPrime(n); return 0; } ``` 代码解释： 1. `checkPrime`函数：该函数接收一个整数`n`作为参数，用于判断`n`是否为质数。 - 首先检查`n`是否小于等于1，如果是，则从2开始遍历寻找`n`的约数，找到后输出该约数并返回。 - 然后从2开始遍历到`n`的平方根，如果`n`能被`i`整除，说明`n`不是质数，输出`i`（即第二小的约数）并返回。 - 如果遍历完都没有找到除1和自身以外的约数，说明`n`是质数，输出`Yes`。 2. `main`函数：读取用户输入的正整数`n`，并调用`checkPrime`函数进行判断。 复杂度分析： - 时间复杂度：$O(\sqrt{n})$，因为只需要遍历到$\sqrt{n}$。 - 空间复杂度：$O(1)$，只使用了常数级的额外空间。 ######[AI问答 | 529点数解答 | 2025-11-22 17:09:28]