C++如何进行快速素数筛法（埃氏筛/欧拉筛）？（预生成质数表）

埃氏筛不超时的关键是优化内存访问与边界处理：用vector反而更慢，循环变量用int或size_t，内层从i*i开始标记，筛后可预存质数列表。

埃氏筛怎么写才不超时？ 埃氏筛的效率瓶颈不在算法本身，而在内存访问模式和边界处理。用 vector<bool></bool> 看似省空间，实际因位压缩导致频繁掩码操作，反而比 vector<char></char> 慢 2–3 倍；筛到 n 时只需枚举到 sqrt(n)，但循环变量类型必须是 int 或 size_t，若用 unsigned int 在 n 接近 UINT_MAX 时可能整数溢出。

• 初始化数组大小为 n + 1，索引直接对应数值，is_prime[0] = is_prime[1] = false
• 外层循环从 2 到 sqrt(n)（用 i * i 判断，避免浮点运算）
• 内层从 i * i 开始标记，步长为 i：因为更小的倍数已被更小的质数筛过
• 若需频繁查质数，筛完后可额外构建一个 vector<int></int> 存所有质数，避免每次遍历判断

vector<char> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;
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] = false;
        }
    }
}

欧拉筛为什么快？关键在“每个合数只被最小质因子筛一次” 欧拉筛（线性筛）真正优势不是理论复杂度，而是缓存友好：内层循环中，primes 向量是连续访问，is_prime 数组也是按顺序写入，CPU 预取效率高。但它对初始化和边界极其敏感——如果漏判 i % primes[j] == 0 就会退化成埃氏筛；若 primes[j] 超过 i 的最小质因子，继续筛就会重复标记。

• 必须用 vector<int></int> 存质数，不能用 vector<size_t></size_t> 混用，否则比较时隐式转换易出错
• 内层循环中，一旦 i % primes[j] == 0 就立刻 break，这是保证线性的唯一条件
• i * primes[j] 可能溢出，务必转成 long long 判断是否 ≤ n
• 不要试图“优化”掉 is_prime 数组——它用于快速查询，而质数列表只用于筛，二者不可替代

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

筛完之后怎么高效查某个数是不是质数？ 别在运行时反复调用筛函数，预筛后查表才是正解。但要注意：vector<char></char> 支持 O(1) 随机访问，而 vector<bool></bool> 不支持取地址、不能用 data()，且迭代器行为异常，任何涉及指针或底层内存操作（比如传给 SIMD 函数）都会出问题。

• 查单个数：直接访问 is_prime[x]，前提是 x 在 [0, n] 范围内，否则越界未定义
• 查区间内质数个数：可用前缀和数组 cnt[i] 表示 ≤ i 的质数个数，构造时间 O(n)，查询 O(1)
• 若 n 很大（如 1e8），建议用 std::vector<char></char> + std::ios::sync_with_stdio(false) 加速输入输出，避免流缓冲拖慢

常见崩溃/错误现象和对应原因vector<bool></bool> 导致的段错误往往出现在多线程写同一位置，或者用 &is_prime[i] 取地址；std::bad_alloc 不一定是内存不够，也可能是 n 超过 size_t 最大值导致 vector 构造时计算长度溢出；筛出来的质数列表里出现合数，基本是欧拉筛中漏了 break 或 primes[j] 访问越界。

• 错误：筛出 4 或 9 在质数列表里 → 检查欧拉筛内层是否在 i % primes[j] == 0 后正确 break
• 错误：is_prime[2] == false → 初始化没设 is_prime[2] = true，或循环从 1 开始覆盖了
• 错误：程序在 i = 65536 附近卡住 → 外层循环用 int i 但 n > INT_MAX，改用 long long i 或确保 n 在安全范围内

筛法不是黑盒工具，i * i 会不会溢出、vector<bool></bool> 怎么悄悄拖慢你、break 少写一次就破功——这些细节全在临界点上咬着性能和正确性。

星月写作

专为网络小说、 剧本创作者打造的AI增效工具

下载