C++怎么求素数 C++判断质数的高效算法代码【练习】_网络技术

只需检查到√n即可，因若n有大于√n的因子，则必有小于√n的对应因子；循环边界用i≤(int)sqrt(n)或i*i≤n，避免浮点误差。

怎么用 `sqrt` 优化素数判断，避免超时

直接从 2 循到 n-1 判断整除，时间复杂度是 O(n)，对单个数还行，但遇到多次调用或大数（比如 10⁶ 级别）就明显卡顿。核心优化点是：如果 n 有大于 sqrt(n) 的因子，那它一定同时有一个小于 sqrt(n) 的对应因子。所以只需检查到 sqrt(n) 即可。

注意：sqrt(n) 返回浮点数，循环边界要用 i (sqrt(n)) + 1 或更稳妥的 i * i （避免浮点误差和类型转换开销）。

对 n == 1 要特判返回 false；n == 2 是唯一偶质数，要单独返回 true
可以先排除所有偶数（除了 2），后续只试奇数，再省一半时间
sqrt 在中，记得包含

写一个通用的 `is_prime` 函数要注意哪些边界

常见错误不是算法错，而是没处理好小数字和负数。C++ 标准里「质数」定义是大于 1 的自然数，所以 n 必须返回 false；n == 2 返回 true；n % 2 == 0 且 n != 2 就直接 false。

示例代码片段：

bool is_prime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

不要用 double s = sqrt(n); for (int i = 3; i —— sqrt 可能因精度丢位，比如 n == 2147395600（=46340²）时，sqrt 可能算成 46339.999，转 int 后变 46339，漏掉关键因子
用 i * i 安全，但注意 i * i 可能溢出（尤其 n 接近 INT_MAX），此时应改用 i

需要批量判断 1~N 内所有素数？用埃氏筛还是线性筛

如果只是判断几个数，用上面的 is_prime 就够了；但如果要查 1~10⁶ 范围内全部素数（比如做预处理、打表），就得上筛法。埃氏筛（std::vector 实现）写起来简单、内存友好，时间复杂度 O(N log log N)，对 10⁷ 以内足够快。

线性筛（欧拉筛）能做到 O(N)，但常数大、代码稍长，且只有在需要「记录每个数最小质因子」或严格卡常时才值得换。

埃氏筛记得从 i*i 开始标记，不是从 2*i —— 前者避免重复标记，后者会多做很多无用操作
数组大小设为 N+1，索引直接对应数值，prime[0] 和 prime[1] 初始化为 false
筛完后遍历一遍数组就能收集所有素数，不用额外维护列表

用 `long long` 判断大数时为什么容易出错

当 n 是 long long 类型（比如 10¹² 级别），上面的 i * i 会溢出 —— i 是 int，乘出来还是 int，结果截断。必须统一用 long long 类型变量做循环和乘法。

同时，sqrt(n) 对 long long 不安全（sqrt 没有 long long

重载，会转成 double，而 double 只有 53 位有效精度，无法精确表示大于 2⁵³ 的整数）。

正确做法：用 long long i = 3; i —— 除法不会溢出，且语义清晰
别忘了 n 本身可能是 long long，函数参数得声明为 long long n
对于 >10¹⁴ 的数，单靠试除已不够，得考虑 Miller-Rabin 等概率算法，但那是另一层复杂度了

实际写的时候，最常被忽略的是小值特判和整数溢出边界——尤其是从 int 切换到 long long 时，循环变量类型、乘法、比较操作都得同步改，漏一个就跑错。

# 显卡 # c++ # 质数 # int # 循环 # 算法 # 浮点 # 只需 # 是从 # 的是 # 那是 # 就能 # 遍历 # 设为 # 一遍 # 要注意

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】