只需试除到√n即可判断素数，因若n有大于√n的因数，则必有对应小于√n的因数；注意n=1、n=2等边界情况需单独处理。
用 sqrt(n) 优化试除法判断素数
直接从 2 试除到 n-1 效率太低，多数情况下没必要。真正只需检查到 sqrt(n) —— 因为如果 n 有大于 sqrt(n) 的因数，那它一定对应一个小于 sqrt(n) 的因数。
注意边界处理：n 不是素数；n == 2 是唯一偶素数；所有其他偶数可直接返回 false。
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) { // i*i 避免浮点 sqrt，且只试奇数
if (n % i == 0) return false;
}
return true;
}处理大整数时的溢出风险
i * i 在 n 接近 INT_MAX 时，i * i 可能溢出变成负数，导致循环失控或误判。安全做法是改用 i （整除）。
-
n / i是整数除法，不会溢出，且语义等价于i - 当
i > n / i时，说明i * i > n，可安全退出 - 对
long long类型也适用，无需额外类型转换
bool is_prime(long long n) {
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (long long i = 3; i <= n / i; i += 2) {
if (n % i == 0) return false;
}
return true;
}多次调用场景下考虑预筛小素数
如果要频繁判断多个数（比如在算法题中批量验证 1e5 个数），每次都从头试除不划算。可以预先用埃氏筛生成一个布尔数组 is_prime_up_to_1000000，之后查表即可。
立即学习“C++免费学习笔记（深入）”；
但注意：预筛只适合已知上界的情况；若单次判断一个极大数（如 1e18），筛法不可行，仍得靠优化试除或 Miller-Rabin。
- 筛到
1e6只需约 1ms，内存占用 ~1MB - 筛后每次查询是
O(1)，比试除快两个数量级 - 筛本身不解决大数问题，只是“以空间换时间”的权衡
误用 double sqrt(n) 导致精度错误
有人写 for (int i = 2; i ，这很危险。因为 sqrt 返回 double，浮点计算有精度误差，比如 sqrt(25) 可能算成 4.9999999，转成 int 就变 4，漏掉 5 这个因数。
- 永远不要对整数开方后强转
int做循环上界 - 要么用
i （推荐） - 要么用
sqrtl(n) + 1e-9向上取整，但多此一举 - 更糟的是混用
sqrt和i*i：前者可能截断，后者可能溢出，两头不讨好
实际写的时候，is_prime 看似简单，但边界、溢出、精度三处最容易翻车。尤其在线判题中，n = 2147483647（INT_MAX）这种数据专打 i*i 溢出和 sqrt 截断。
