答案是判断质数需检查2到√n的因数。若n大于1且无小于等于√n的因数，则为质数，如代码所示，时间复杂度优化至O(√n)。
判断一个数是否是质数在C++中是一个常见的编程问题。质数是指大于1且只能被1和它本身整除的自然数。例如：2、3、5、7、11等。
基本思路
要判断一个整数n是否为质数，最直接的方法是尝试用从2到n-1的所有数去除n，如果存在能整除的数，则n不是质数。但这种方法效率较低，可以进行优化。
高效判断方法（推荐）
只需检查从2到√n之间的所有整数即可。因为如果n有一个大于√n的因数，那么必然有一个小于√n的对应因数。
示例代码：
#include <iostream><br>#include <cmath><br>using namespace std;<br><br>bool isPrime(int n) {<br> if (n <= 1) return false; // 小于等于1的数不是质数<br> if (n == 2) return true; // 2是质数<br> if (n % 2 == 0) return false; // 偶数（除了2）不是质数<br><br> int limit = sqrt(n);<br> for (int i = 3; i <= limit; i += 2) {<br> if (n % i == 0)<br> return false;<br> }<br> return true;<br>}<br><br>int main() {<br> int num;<br> cout << "请输入一个整数：";<br> cin >> num;<br><br> if (isPrime(num))<br> cout << num << " 是质数。" << endl;<br> else<br> cout << num << " 不是质数。" << endl;<br><br> return 0;<br>}
关键点说明
- 处理边界情况：n ≤ 1 返回 false，n == 2 返回 true
- 排除偶数能大幅提升效率，循环只检查奇数
- 使用 sqrt(n) 作为循环上限，避免不必要的计算
- 包含头文件
才能使用 sqrt 函数
基本上就这些。这个方法对于一般用途已经足够高效，适用于大多数场景下的质数判断。
立即学习“C++免费学习笔记（深入）”；
