答案是判断质数需检查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
#include
using namespace std;
bool isPrime(int n) {
if (n <= 1) return false; // 小于等于1的数不是质数
if (n == 2) return true; // 2是质数
if (n % 2 == 0) return false; // 偶数（除了2）不是质数
int limit = sqrt(n);
for (int i = 3; i <= limit; i += 2) {
if (n % i == 0)
return false;
}
return true;
}
int main() {
int num;
cout << "请输入一个整数：";
cin >> num;
if (isPrime(num))
cout << num << " 是质数。" << endl;
else
cout << num << " 不是质数。" << endl;
return 0;
}
关键点说明
- 处理边界情况：n ≤ 1 返回 false，n == 2 返回 true
- 排除偶数能大幅提升效率，循环只检查奇数
- 使用 sqrt(n) 作为循环上限，避免不必要的计算
- 包含头文件
才能使用 sqrt 函数
基本上就这些。这个方法对于一般用途已经足够高效，适用于大多数场景下的质数判断。
立即学习“C++免费学习笔记（深入）”；
