正确素数判断函数应先特判n
怎么用 C++ 写一个正确的素数判断函数
最直接的办法是写一个 is_prime(int n)，但很多人一上来就从 2 循到 n-1，这在 n 较大时完全不可行。正确做法是只试除到 sqrt(n)，且必须注意边界处理：小于 2 的数（如 0、1、负数）都不是素数；2 是素数；偶数（除 2 外）直接返回 false。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 先特判
n → return false；n == 2→ return true；n % 2 == 0→ return false - 循环从
i = 3开始，每次i += 2，上限设为i * i （比i 更安全，避免浮点误差和类型转换开销） - 不要用
sqrt((double)n)做循环条件——浮点精度可能让最后一次迭代被跳过
C++ 中 int 范围内素数判断的性能瓶颈在哪
瓶颈不在算法逻辑本身，而在整数溢出和重复取模。比如当 n 接近 INT_MAX（约 2.1e9）时，i * i 在 i 约 46340 就会溢出 int，导致未定义行为。另外，对每个奇数都做 % 运算，在现代 CPU 上虽快，但分支预测失败（比如大量小素数输入）仍会拖慢。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 把循环变量
i声明为long long，或改用i 避免乘法溢出（推荐，无额外类型转换） - 如果批量判断（如筛法前预处理），可先排除 2 和 3 的倍数，再用 6k±1 优化：所有素数 > 3 都形如 6k−1 或 6k+1
- 对单次调用，6k±1 优化收益有限，还增加代码复杂度，不建议盲目套用
为什么 std::sqrt 不该出现在素数判断的 for 条件里
因为 std::sqrt 返回 double，而 double 对大于 253 的整数无法精确表示。即使 n 是 int，强制转 double 后再开方、再转回整数，可能向下取整错误。更隐蔽的问题是：编译器可能把 sqrt(n) 提取到循环外，但若 n 是 signed int 且为负，sqrt 返回 NaN，比较结果未定义。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 用
i 替代i —— 整数运算，无精度损失，无符号/浮点转换 - 如果非要用
sqrt，至少写成(long long)sqrt((long double)n) + 1并加校验，但纯属绕远路 - Clang/GCC 在
-O2下对i * i 会自动优化为无溢出检查的指令，但前提是i类型足够宽，否则仍得靠n / i
时间复杂度到底是 O(√n) 还是更低
理论是 O(√n)，但常数因子差异极大。朴素版（2 到 n−1）是 O(n)；基础优化版（2 和奇数到 √n）是 O(√n)；6k±1 版本把常数压到约 1/3，仍是 O(√n)。真正影响实际耗时的是：CPU 分支预测是否成功、除法指令延迟、缓存是否命中（对连续小数字频繁调用时尤其明显）。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 别迷信“更优”的渐进复杂度——对
n ，甚至试除到 √n 都很快；对n > 1e12，单次判断已不现实，应换 Miller-Rabin - 如果真要测性能，用
volatile int dummy = is_prime(x);防止编译器优化掉整个调用 - 记住：O(√n) 是最坏情况（n 是素数），而合数往往在很小的因子就返回，平均远快于 √n
最易被忽略的一点：没有“万能最优解”。输入分布决定策略——如果你总在判断形如 4k+3 的数，提前试除 3 和 7 可能比通用循环更快；而线上服务中，缓存已知小素数表（如前 100 个）反而比每次计算更稳。
