答案是使用优化试除法判断素数：先处理边界情况，再只检查奇数因子至√n。bool isPrime(int n) { if (n ≤ 1) return false; if (n == 2) return true; if (n > 2 && n % 2 == 0) return false; for (int i = 3; i * i
判断一个数是否为素数是C++编程中常见的问题。素数是指大于1且只能被1和自身整除的自然数。最直接的方法是试除法，但效率较低。下面介绍一种高效且实用的素数判断算法实现。
基本思路与优化策略
要判断一个数n是否为素数，不需要从2试除到n-1，只需检查从2到√n之间的所有整数即可。因为如果n有大于√n的因子，那么必然有一个小于√n的对应因子。
进一步优化：
• 若 n ≤ 1，不是素数• 若 n == 2，是素数（唯一偶数素数）
• 若 n > 2 且为偶数，不是素数
• 只需检查从3开始的所有奇数到√n
C++高效实现代码
以下是经过优化的素数判断函数：
立即学习“C++免费学习笔记（深入）”；
bool isPrime(int n) {
if (n
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i * i
if (n % i == 0)
return false;
}
return true;
}
使用示例
你可以这样调用该函数：
#include
using namespace std;
int main() {
int num = 97;
if (isPrime(num))
cout
else
cout
return 0;
}
时间复杂度分析
该算法的时间复杂度为O(√n)，相比暴力方法提升显著。对于大数判断已足够高效。若需频繁判断或处理更大范围，可考虑埃氏筛或线性筛预处理素数表。
基本上就这些，这个版本在大多数场景下已经足够快，也易于理解和维护。注意使用i * i 而不是i ，避免浮点运算带来的精度问题和性能开销。
