17370845950

埃氏筛不超时的关键是只筛到√n且内层从i²开始：数组大小≥n+1，is_prime[0]和[1]置false，外层i≤√n，内层j从i²起步并检查j≤n，避免重复筛和溢出。

埃氏筛（Eratosthenes Sieve）怎么写才不超时

埃氏筛的核心是：从 2 开始，把每个素数的倍数全部标记为合数。关键不是“筛多少”，而是“别重复筛”。常见错误是内层循环从 i * i 开始却忘了加边界检查，或用 int 存大数导致溢出。

正确写法要点：

• 数组大小必须 ≥ n + 1，下标直接对应数字，is_prime[0] 和 is_prime[1] 初始化为 false
• 外层只遍历到 sqrt(n)（即 i * i ），再大就无新倍数可筛
• 内层从 i * i 开始标记，因为更小的倍数（如 2*i, 3*i）已被更小的素数筛过
• 用 vector 节省内存，但注意它不是标准容器——若需取地址或迭代器操作，换 vector

vector sieve_eratosthenes(int n) {
    vector is_prime(n + 1, 1);
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i * i <= n; ++i) {
        if (is_prime[i]) {
            for (long long j = (long long)i * i; j <= n; j += i) {
                is_prime[j] = 0;
            }
        }
    }
    return is_prime;
}

欧拉筛（线性筛）为什么能 O(n)？关键在“最小质因子”

欧拉筛不是“每个合数被所有质因子筛”，而是“每个合数只被它的最小质因子筛一次”。这靠两个判断实现：当 i % primes[j] == 0 时立刻 break。否则会用更大的质数去筛同一个数，破坏线性。

常见误写：

• 没在 i % primes[j] == 0 后 break → 变成埃氏筛，时间退化为 O(n log log n)
• 内层循环条件写成 j → 逻辑错，应是 primes[j] * i
• 用 int 计算 primes[j] * i 溢出 → 必须转 long long 判断上界

vector sieve_euler(int n) {
    vector is_prime(n + 1, 1);
    vector primes;
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) primes.push_back(i);
        for (int j = 0; j < (int)primes.size(); ++j) {
            long long p = (long long)primes[j] * i;
            if (p > n) break;
            is_prime[p] = 0;
            if (i % primes[j] == 0) break;
        }
    }
    return is_prime;
}

埃氏筛 vs 欧拉筛：什么时候该选哪个

欧拉筛理论快，但常数大、缓存不友好；埃氏筛简单、局部性好，实际在 n ≤ 1e7 时往往更快。别盲目追求“O(n)”。

• 选埃氏筛：只要求快速预处理、n 在 1e6～1e7、代码要短且易 debug
• 选欧拉筛：n ≥ 1e8、需要同时获取质数列表、题目强制卡常（如 ACM 现场赛）、后续要频繁查第 k 个素数
• 都别用：n > 1e9 → 改用分段筛（segmented sieve）或 Miller-Rabin 随机测试

内存方面，两者都是 O(n)，但欧拉筛多一个 primes 数组，约存 π(n) ≈ n / ln n 个 int，对 1e8 就多占 ~5MB。

真实项目中容易忽略的细节

竞赛或工程里，筛法不是“写完就跑”，常卡在边界和类型上：

• n = 0 或 n = 1 时，埃氏筛的 i * i 不进循环，但 is_prime 大小仍要 ≥ n + 1，否则访问越界
• 用 vector 返回后，不能对元素取地址（

  

  &is_prime[i] 是非法的），调试时容易段错误
• 多线程环境下，埃氏筛可并行外层（每个线程负责一段 i），但欧拉筛必须串行——它依赖 primes 的实时增长
• 如果只需判断单个大数是否为素数，筛法完全不合适，应直接试除到 sqrt(n) 或用 std::is_prime（C++20）

最麻烦的其实是“筛完怎么用”：比如要统计 [L, R] 内素数个数，别急着开 1e9 大小数组——先筛 √R，再用分段筛更稳妥。