用 sqrt 优化素数判断的核心是只试除到 √n，将时间复杂度从 O(n) 降至 O(√n)，但需注意浮点误差与整型截断，故上限应取 floor(√n)+1 以确保正确性。
用 sqrt 优化素数判断，核心是只试除到 √n
直接遍历 2 到 n−1 效率太低，C++ 中用 sqrt 将时间复杂度从 O(n) 降到 O(√n)，这是质数判定最基础也最关键的优化。注意：不是所有场景都适合用 sqrt，比如 n 很小（
关键点：
-
sqrt返回double，必须转为整型上限（如(int)sqrt(n) + 1），否则因浮点误差可能漏判边界（例如 n=25，sqrt(25)理论上是 5.0，但某些平台可能略小于 5.0，取整后变 4） - 别在循环条件里反复调用
sqrt(n)，应提前算一次存为变量 - 必须特判
n （非素数）、n == 2（唯一偶素数）
C++ 实现带边界处理的 is_prime 函数
以下是最常用、兼顾正确性与效率的写法，已处理常见坑点：
bool is_prime(int n) {
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false; // 排除其他偶数
int limit = (int)sqrt(n) + 1; // +1 确保覆盖整数边界
for (int i = 3; i < limit; i += 2) { // 只试奇数
if (n % i == 0) return false;
}
return true;
}
说明：
立即学习“C++免费学习笔记（深入）”；
- 跳过所有偶数（除 2 外），循环步长设为 2，进一步减半尝试次数
-
limit用(int)sqrt(n) + 1而非(int)sqrt(n)，避免因浮点舍入导致i最大只到 4（当 n=25）而漏掉 5 - 若 n 是完全平方数（如 49），它的最小非平凡因子 ≤ √n，所以这个上限逻辑成立
为什么不用 sqrtf 或 sqrtl？
对 int 范围内的 n（通常 ≤ 2×10⁹），sqrt（即 sqrt(double)）精度足够；sqrtf 是单精度，32 位 float 在表示大于 2²⁴ 的整数时会丢失精度，可能导致 (int)sqrtf(16777217) 错误地等于 4096 而非 4097；sqrtl 过重，且无必要。实际项目中统一用 sqrt + 显式 +1 更稳妥。
另外注意：
- 编译时需链接 math 库：
g++ -o prime prime.cpp -lm（Linux/macOS） - 头文件只需
#include，无需 - 如果 n 是
long long类型，sqrt无法直接处理，此时应改用整数二分求平方根，或用sqrtl+ 更谨慎的边界修正
小数据用查表，大数据考虑 Miller-Rabin
当频繁判断多个数（比如筛 10⁶ 以内所有素数），用 sqrt 单个判断仍是 O(√n) 级别，总代价高；此时应该换思路：
- ≤ 10⁶：直接埃氏筛预处理布尔数组，O(n log log n)，后续 O(1) 查询
- 单个数 > 10⁹：
sqrt法仍可行（√n ≈ 31623），但若需更高可靠性（比如密码学场景），应上Miller-Rabin概率算法 - 注意：
sqrt法对合数很快能返回 false，但对大素数必须跑满循环，这是它最慢的情况
真正容易被忽略的是——浮点误差和整型截断的组合效应，哪怕只差 1，就可能让一个形如 p² 的合数（如 1000000007²）被误判为素数。所以加 +1 不是“多此一举”，而是数学严谨性的落地细节。
