欧拉筛算法：线性时间复杂度的质数筛选技术

1. 为什么我们需要欧拉筛？

在C++编程中，质数判断和生成是一个经典问题。初学者通常会先学会最基础的暴力判断法——对于每个待检测的数n，从2遍历到√n，检查是否能整除。这种方法虽然直观，但当需要处理大量数据时，其O(n√n)的时间复杂度就显得力不从心了。

埃拉托斯特尼筛法（埃氏筛）是一个显著的改进，它通过标记倍数的方式筛除非质数，时间复杂度降到了O(n log log n)。但埃氏筛存在一个明显缺陷：它会重复标记合数。比如数字6会被2和3各标记一次，数字30会被2、3、5各标记一次。这种重复标记在数据量很大时会造成不小的性能损耗。

欧拉筛（Euler's Sieve）正是为了解决这个问题而生的。它通过一种巧妙的机制确保每个合数只被其最小质因数筛除一次，将时间复杂度优化到了真正的线性O(n)。对于需要处理百万级甚至更大范围内质数的场景，这种优化带来的性能提升是惊人的。

2. 欧拉筛的核心原理剖析

2.1 算法的工作机制

欧拉筛的精妙之处在于它维护了一个质数表，并遵循以下规则：

1. 遍历从2开始的每个整数i
2. 如果i未被标记为合数，则将其加入质数表
3. 遍历当前质数表中的每个质数p：
   • 将p*i标记为合数
   • 当i能被p整除时立即终止内层循环

关键点在于第三步的提前终止。这个操作保证了每个合数只会被其最小质因数标记一次。例如：

• 当i=4时，质数表中有[2,3]
  • 标记2×4=8，然后发现4能被2整除，终止
  • 这样12就不会在i=4时被3标记（因为3×4=12），而是留到i=6时被2标记（2×6=12）

2.2 数学证明

为什么这个算法能确保线性复杂度？我们可以从数论角度理解：

每个合数n都可以表示为n = p×m，其中p是n的最小质因数。在欧拉筛中：

1. 当外层循环到m时，p已经在质数表中（因为p≤m）
2. 标记p×m后，如果发现m能被p整除，说明m包含p这个因子
3. 此时对于任何大于p的质数q，q×m的最小质因数应该是p而不是q（因为p|m）
4. 因此后续标记应该留给p×k（其中k=m×q/p），避免重复标记

这种机制严格保证了每个合数只被标记一次，实现了真正的线性时间复杂度。

3. C++实现详解

3.1 基础实现代码

下面是一个标准的欧拉筛实现，附带详细注释：

cpp复制#include <vector>
#include <cstring> // for memset

std::vector<int> eulerSieve(int n) {
    std::vector<int> primes; // 存储质数的容器
    bool* isComposite = new bool[n + 1]; // 标记数组
    memset(isComposite, 0, sizeof(bool) * (n + 1)); // 初始化为false
    
    for (int i = 2; i <= n; ++i) {
        if (!isComposite[i]) {
            primes.push_back(i); // i是质数，加入列表
        }
        // 遍历当前已找到的质数
        for (size_t j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            isComposite[i * primes[j]] = true; // 标记合数
            if (i % primes[j] == 0) { // 关键终止条件
                break;
            }
        }
    }
    
    delete[] isComposite;
    return primes;
}

3.2 关键代码解析

1. 内存分配：使用动态分配的bool数组作为标记，比vector更高效。注意要手动释放内存。
2. 外层循环：从2开始遍历每个数i，判断其是否为质数。
3. 内层循环：用当前i与所有已找到的质数相乘，标记其乘积为合数。
4. 提前终止：if (i % primes[j] == 0) break; 这是保证线性的关键。
5. 边界检查：i * primes[j] <= n 防止数组越界。

3.3 性能优化技巧

1. 内存优化：可以使用bitset代替bool数组，将内存占用减少到1/8。

   cpp复制#include <bitset>
   std::bitset<10000001> isComposite; // 静态大小，编译时确定
   

2. 循环优化：将乘法和比较操作提到循环外：

   cpp复制for (size_t j = 0; (p = primes[j]) && (m = i * p) <= n; ++j) {
       isComposite[m] = true;
       if (i % p == 0) break;
   }
   

3. 缓存友好：对小范围质数可以先筛选并缓存，分段处理超大范围。

4. 实战应用场景

4.1 质因数分解加速

欧拉筛预处理质数表后，可以极大加速质因数分解：

cpp复制std::vector<int> factorize(int x, const std::vector<int>& primes) {
    std::vector<int> factors;
    for (int p : primes) {
        if (p * p > x) break;
        while (x % p == 0) {
            factors.push_back(p);
            x /= p;
        }
    }
    if (x > 1) factors.