c++怎么判断一个数是否为素数_c++求质数算法【实战】

素数判断需先处理边界：n

判断一个数是否为素数：从边界条件开始检查

小于2的数（如0、1、负数）直接不是素数，这是最容易忽略的起点。c++中int类型输入若未校验，is_prime(-5)或is_prime(1)返回true就是典型错误。

• 必须先判断 n ，立即返回 false
• n == 2 是唯一偶素数，需单独返回 true
• n % 2 == 0 && n != 2 的情况直接返回 false

优化试除法：只遍历到 sqrt(n)

对正整数n，若它有大于sqrt(n)的因子，则必有一个对应的小于sqrt(n)的因子。因此循环上限设为(int)sqrt(n)或更安全的i * i ——后者避免浮点误差和#include 依赖。

• 用 for (int i = 3; i * i ，跳过所有偶数
• 注意 i * i 可能溢出（尤其n接近INT_MAX），此时应改用 i
• 不要写 i ：多次调用sqrt低效，且sqrt返回double可能因精度丢位（如sqrt(25)返回4.999999导致循环少一次）

处理大数或多次查询：考虑简单预处理

单次判断用试除法足够；但若需在[2, 10⁵]范围内频繁查素数（比如做1000次is_prime(x)），埃氏筛更高效。不过别一上来就写筛法——它空间开销固定，对稀疏查询反而浪费。

• 小范围（n ）且查询密集：用vector is_prime(N+1, true) + 埃氏筛预处理
• 大n（如10⁹量级）：试除法仍是首选，但需加6k±1优化（跳过所有2、3的倍数）
• 注意vector是特化容器，某些编译器下operator[]非O(1)原子访问，多线程需额外同步

常见错误与陷阱：溢出、类型、逻辑短路

看似简单的函数，实际在线上环境常因细节崩掉。比如is_prime(2147483647)（INT_MAX）在32位机上跑i * i 会因i递增到46341时i*i溢出成负数，导致无限循环。

立即学习“C++免费学习笔记（深入）”；

• 用 long long i 或改判条件为 i （整除安全）
• 输入参数用 long long 而非 int，避免调用方传入大字面量被截断
• 逻辑表达式中 n % i == 0 必须放在 i * i 之后，否则短路失效引发越界访问
• 别信“if (n == 2) return true; else if (n % 2 == 0) return false;”后就默认n是奇数——万一n是负奇数，n % 2在C++里可能是-1，导致误判

实际写的时候，最麻烦的从来不是“怎么写对”，而是“怎么让边界、溢出、符号、并发这些隐性条件不反咬一口”。把i 和n 这两处写稳，其余就只是节奏问题。