c++如何判断一个数是否为素数_c++质数判断算法优化【技巧】

判断素数只需试除到√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 这种写法，太顺手反而最容易忘掉它有多危险。