判断素数只需试除到√n即可，因若n有大于√n的因数，则必有对应小于√n的因数；注意用i*i≤n避免浮点误差和溢出。
判断素数时别直接试到 n-1
试除法最直观，但效率极低。比如判断 982451653 是否为素数，从 2 试到 n−1 要做近 10 亿次除法——实际完全没必要。
只要试到 sqrt(n) 就够了：如果 n 有大于 sqrt(n) 的因数，那它一定对应一个小于 sqrt(n) 的因数。注意边界处理，i * i 比 <code>i 更安全（避免浮点误差和类型转换开销）。
- 对
n == 1直接返回 false；n == 2返回 true - 偶数（除 2 外）直接返回 false，后续只试奇数
- 循环从
i = 3开始，每次i += 2 - 用
int类型变量存i * i可能溢出，建议用long long或改用i
用 int 还是 long long 做参数？
输入范围决定类型选择。如果函数签名为 bool is_prime(int n)，那它在 n 接近 INT_MAX（约 2.1e9）时，i * i 会溢出成负数，导致循环条件永远成立或崩溃。
更稳妥的做法是统一用 long long 接收，或者改用除法判界：i 。这样即使 <code>n 是 int 最大值，n / i 仍是合法整数运算。
立即学习“C++免费学习笔记（深入）”；
-
is_prime(2147483647)（梅森素数）在int版本里极易因溢出误判 - 若明确只处理
[2, 10^6]范围，int安全，且缓存友好 - 竞赛或通用库中建议用
long long+i
小范围批量判断？别单个调用 is_prime
要判断 1~1000000 中所有素数，反复调用单个 is_prime 函数，时间复杂度是 O(n√n)，约 10¹¹ 次操作，超时是必然的。
这时候该上埃氏筛（sieve_of_eratosthenes）。它用 O(n log log n) 预处理出整个区间的结果，之后查表 O(1)。内存占用约 n/8 字节（用 bitset 优化后）。
- 初始化 vector
或 bitset，标记 0 和 1 为 false - 从 2 开始，把每个素数的倍数全标为 false；只需筛到
sqrt(n) - 注意内层循环起点是
i * i，不是2 * i（更小的倍数已被更小的素数筛过） - vector
是特化类型，访问稍慢；高频查询可用 vector
遇到 runtime error: signed integer overflow 怎么办
这是最常见的实战报错，通常出现在 for (int i = 3; i * i 里。当 <code>n 很大（如 2e9），i 接近 46340 时，i * i 超过 INT_MAX，触发未定义行为。
修复不靠加编译选项，而靠改写逻辑。最直接的是把乘法换成除法：i ，前提是 <code>i > 0（我们保证了）；或者把 i 升级为 long long，但要注意函数参数和循环变量类型一致。
- Clang/GCC 在 -fsanitize=undefined 下会立刻暴露这个问题
- 线上环境没开 sanitizer，这种溢出可能表现为随机 false 正或死循环
- 哪怕只用于本地测试，也建议默认用
i ，零成本且普适
素数判断看着简单，真正写进生产代码或算法题里，溢出、边界、类型匹配、场景误用这四点，任何一个没兜住就容易卡半天。尤其是 i * i 这种写法，太顺手反而最容易忘掉它有多危险。
