试除法判断素数需先处理n≤1返回false、n==2返回true、n为偶数且≠2返回false，再从3开始只试奇数到sqrt(n)。
怎么用试除法快速判断一个 int 是不是素数
对普通范围（比如 1e9 以内）的整数，试除法够用、好写、不易出错。核心是只试到 sqrt(n)，且跳过偶数（除了 2）。
常见错误现象：n == 1 返回 true；n == 0 或负数没处理；循环从 2 试到 n-1 导致超时；没特判 2 就直接跳偶数导致漏判。
- 必须先处理
n → 直接返回 <code>false -
n == 2→ 返回true；n % 2 == 0→ 返回false - 循环从
i = 3开始，每次i += 2，上限设为i * i （避免浮点误差和溢出，比 <code>sqrt(n)更安全） - 用
int类型即可，别用long long增加无谓开销
bool is_prime(int n) {
if (n < 2) 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;
}为什么 int 范围内基本不用米勒-拉宾
米勒-拉宾是概率算法，对 int（32 位有符号，最大约 2.1e9）来说，它带来的复杂度和出错风险远大于收益——确定性测试已有更优解。
使用场景：只有当你要判断 long long（64 位）范围内的数，且无法接受试除法的最坏 O(√n) 时间时，才考虑它。
立即学习“C++免费学习笔记（深入）”；
- 对
int，已知一组小底数（如2, 7, 61）就能做到 100% 准确，但代码量翻倍、易写错模幂和二次探测 - 手写
mulmod（大数乘法取模）极易溢出，用__int128又不跨平台 - 标准库不提供，竞赛中若非必要，评委也默认你用试除法
is_prime 在循环里反复调用很慢？怎么优化
如果要批量判断多个数（比如筛 1e6 个数），每次都调用试除法，重复计算因子太多，性能会断崖式下跌。
这时候该换思路：预处理质数表，而不是单个判断。
- 若最大值 ≤
1e7，直接上埃氏筛（vector<bool> is_prime(N+1, true)</bool>），时间O(N log log N)，之后O(1)查询 - 若最大值更大（如
1e8），用线性筛（欧拉筛），避免重复标记，内存稍多但更快 - 不要在循环里对每个数都调用完整
is_prime——哪怕加了记忆化，也不如一次性筛完干净
边界和类型容易踩的坑
看似简单函数，实际线上崩得最多的是类型和边界——尤其是和输入/输出混用时。
-
is_prime(-5)、is_prime(0)、is_prime(1)必须返回false，数学定义里素数是「大于 1 的正整数」 - 输入是
unsigned int或long long？函数签名不匹配会导致隐式转换出错（比如2147483648U转成int变负数） - 测试用例含
INT_MAX（2147483647）？它的平方远超int范围，所以循环条件必须用i * i 而不是 <code>i ，后者涉及浮点还可能精度丢失
真正麻烦的从来不是算法本身，而是你没意识到 i * i 在 i 接近 46341 时就溢出了，而这个数刚好卡在 int 的 sqrt 边界附近。
