质数判断需排除小数、负数、0、1；试除只需到√n，但要用i*i
怎么写一个靠谱的 is_prime 函数
小数、负数、0、1 都不是质数，这是最容易漏掉的边界。C++ 里没有内置判断，得自己写，但别一上来就试除到 n-1——太慢，也别无脑用 sqrt(n) 而不处理浮点误差。
if (n 必须放最前，否则 <code>2会进错分支- 单独处理
n == 2，返回true；再排除所有偶数：if (n % 2 == 0) return false; - 奇数试除从
3开始，步长为2，上限用i * i （比 <code>(int)sqrt(n)更安全，避免浮点舍入和溢出） - 注意
i * i可能溢出，对大整数（比如long long）应改用i
埃氏筛（sieve_of_eratosthenes）适合什么场景
要批量判断 [2, N] 区间内所有数是否为质数时，单个 is_prime 调用 N 次是 O(N√N)，而埃氏筛是 O(N log log N)，快得多。但它吃内存，且只适用于静态范围。
- 初始化布尔数组
vector<bool> is_prime(N + 1, true)</bool>，is_prime[0] = is_prime[1] = false - 外层循环从
2到sqrt(N)，只处理仍为true的数（即当前最小未标记质数） - 内层从
i * i开始标记，不是2*i——因为更小的倍数已被更小的质因子筛过 -
vector<bool></bool>虽省内存，但访问慢（位压缩），高频查询可换vector<char></char>
线性筛（linear_sieve）比埃氏筛强在哪
线性筛能做到 O(N)，而且能顺便得到每个数的最小质因子（min_prime_factor），这对分解质因数、求欧拉函数等后续操作很关键。但它代码稍长，逻辑更绕，容易写错标记条件。
- 维护两个数组：
vector<int> primes</int>存质数，vector<int> min_p(N + 1)</int>存最小质因子 - 遍历
i从2到N，若min_p[i] == 0，说明没被筛过 →i是质数，加入primes，设min_p[i] = i - 对每个已知质数
p（从小到大），标记i * p：只要p 就继续，否则 <code>break——这是保证每个合数只被其最小质因子筛一次的关键 - 别忘了检查
i * p是否越界（> N），越界就跳过
常见错误：int 溢出和 sqrt 的陷阱
很多人在试除循环里写 for (int i = 2; i ，结果在 <code>n 接近 INT_MAX 时崩：一是 sqrt 返回 double，精度丢失导致循环多跑一次或少跑一次；二是 i * i 在 int 下直接溢出，变成负数，循环永不停。
立即学习“C++免费学习笔记（深入）”；
- 永远不要对整数用
sqrt做循环条件，改用i （整除安全，无浮点误差） - 如果
n是long long，确保i也是long long，否则i * i仍按int算，溢出 - 编译器不会帮你查这种溢出，
-fsanitize=undefined可以抓到，但线上一般不开 - 测试一定要覆盖
2、3、4、97、1000000007、1、0、负数
质数判断看着简单，真正压测或上生产时，边界、类型、溢出、性能三者往往卡在同一行代码里。筛法选哪种，先想清楚你要的是单次查询、区间批量、还是附带最小质因子——选错方案，后面全白调。
