只需检查到√n即可，因若n有大于√n的因子，则必有小于√n的对应因子；循环边界用i≤(int)sqrt(n)或i*i≤n，避免浮点误差。
怎么用 sqrt 优化素数判断，避免超时
直接从 2 循到 n-1 判断整除，时间复杂度是 O(n)，对单个数还行，但遇到多次调用或大数（比如 10⁶ 级别）就明显卡顿。核心优化点是：如果 n 有大于 sqrt(n) 的因子，那它一定同时有一个小于 sqrt(n) 的对应因子。所以只需检查到 sqrt(n) 即可。
注意：sqrt(n) 返回浮点数，循环边界要用 i (sqrt(n)) + 1 或更稳妥的 i * i （避免浮点误差和类型转换开销）。
- 对
n == 1要特判返回false；n == 2是唯一偶质数，要单独返回true - 可以先排除所有偶数（除了 2），后续只试奇数，再省一半时间
-
sqrt在<cmath>中，记得包含
写一个通用的 is_prime 函数要注意哪些边界
常见错误不是算法错，而是没处理好小数字和负数。C++ 标准里「质数」定义是大于 1 的自然数，所以 n 必须返回 <code>false；n == 2 返回 true；n % 2 == 0 且 n != 2 就直接 false。
示例代码片段：
立即学习“C++免费学习笔记（深入）”；
bool is_prime(int n) {
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0) return false;
}
return true;
}- 不要用
double s = sqrt(n); for (int i = 3; i <= s; ...)——sqrt可能因精度丢位，比如n == 2147395600（=46340²）时，sqrt可能算成 46339.999，转 int 后变 46339，漏掉关键因子 - 用
i * i <= n安全，但注意i * i可能溢出（尤其n接近INT_MAX），此时应改用i <= n / i
需要批量判断 1~N 内所有素数？用埃氏筛还是线性筛
如果只是判断几个数，用上面的 is_prime 就够了；但如果要查 1~10⁶ 范围内全部素数（比如做预处理、打表），就得上筛法。埃氏筛（std::vector<bool> 实现）写起来简单、内存友好，时间复杂度 O(N log log N)，对 10⁷ 以内足够快。
线性筛（欧拉筛）能做到 O(N)，但常数大、代码稍长，且只有在需要「记录每个数最小质因子」或严格卡常时才值得换。
- 埃氏筛记得从
i*i开始标记，不是从2*i—— 前者避免重复标记，后者会多做很多无用操作 - 数组大小设为
N+1，索引直接对应数值，prime[0]和prime[1]初始化为false - 筛完后遍历一遍数组就能收集所有素数，不用额外维护列表
用 long long 判断大数时为什么容易出错
当 n 是 long long 类型（比如 10¹² 级别），上面的 i * i <= n 会溢出 —— i 是 int，乘出来还是 int，结果截断。必须统一用 long long 类型变量做循环和乘法。
同时，sqrt(n) 对 long long 不安全（sqrt 没有 long long 重载，会转成 double，而 double 只有 53 位有效精度，无法精确表示大于 2⁵³ 的整数）。
- 正确做法：用
long long i = 3; i <= n / i; i += 2—— 除法不会溢出，且语义清晰 - 别忘了
n本身可能是long long，函数参数得声明为long long n - 对于 >10¹⁴ 的数，单靠试除已不够，得考虑 Miller-Rabin 等概率算法，但那是另一层复杂度了
实际写的时候，最常被忽略的是小值特判和整数溢出边界——尤其是从 int 切换到 long long 时，循环变量类型、乘法、比较操作都得同步改，漏一个就跑错。
