欧拉筛（线性筛）算法详解：C++实现与质因数分解

什么是欧拉筛？

欧拉筛（Euler’s Sieve），又称线性筛，是一种用于快速找出一定范围内所有质数的算法。由数学家欧拉发明，其核心优势是每个合数只会被其最小的质因子标记一次，实现了真正的 O(n) 时间复杂度。

传统埃拉托斯特尼筛法的不足

在介绍欧拉筛之前，我们先看看传统的埃拉托斯特尼筛法（Sieve of Eratosthenes）：

// 埃拉托斯特尼筛法 - 时间复杂度 O(n log log n)
vector<bool> 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 (int j = i * i; j <= n; j += i) {
            is_prime[j] = false;
        }
    }
}

问题在于：每个合数会被多个质数标记（如12会被2和3都标记），导致效率不是最优。

欧拉筛的核心思想

欧拉筛通过以下关键优化解决重复标记问题：

每个合数只被其最小的质因子筛去

实现这一思想的关键是：在遍历质数时，一旦质数大于当前数的最小质因子，就停止遍历。

C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

// 欧拉筛（线性筛）求质数
vector<int> euler_sieve(int n) {
    vector<int> primes;       // 存储所有质数
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        
        // 关键：遍历所有已知质数
        for (int p : primes) {
            long long x = 1LL * i * p;
            if (x > n) break;           // 超出范围，停止
            
            is_prime[x] = false;        // 标记为合数
            
            // 核心优化：p 是 i 的质因子时停止
            // 这样保证每个合数只被最小质因子筛去
            if (i % p == 0) break;
        }
    }
    
    return primes;
}

// 扩展：同时计算每个数的最小质因子
void euler_sieve_with_spf(int n, vector<int>& primes, vector<int>& spf) {
    spf.assign(n + 1, 0);
    
    for (int i = 2; i <= n; i++) {
        if (spf[i] == 0) {
            spf[i] = i;
            primes.push_back(i);
        }
        
        for (int p : primes) {
            long long x = 1LL * i * p;
            if (x > n) break;
            
            spf[x] = p;  // p 是 x 的最小质因子
            
            if (p == spf[i]) break;
        }
    }
}

// 利用 SPF 进行质因数分解
vector<pair<int, int>> factorize(int n, const vector<int>& spf) {
    vector<pair<int, int>> factors;
    
    while (n > 1) {
        int p = spf[n];
        int cnt = 0;
        while (n % p == 0) {
            n /= p;
            cnt++;
        }
        factors.push_back({p, cnt});
    }
    
    return factors;
}

int main() {
    int n = 100;
    vector<int> primes = euler_sieve(n);
    
    cout << "1到" << n << "的所有质数: " << endl;
    for (int p : primes) {
        cout << p << " ";
    }
    cout << endl;
    
    // 扩展：计算最小质因子
    vector<int> spf;
    euler_sieve_with_spf(n, primes, spf);
    
    cout << "\n最小质因子表: " << endl;
    for (int i = 2; i <= n; i++) {
        cout << "spf[" << i << "] = " << spf[i] << endl;
    }
    
    // 质因数分解示例
    int num = 36;
    vector<pair<int, int>> factors = factorize(num, spf);
    cout << "\n" << num << "的质因数分解: ";
    for (auto [p, cnt] : factors) {
        cout << p << "^" << cnt << " ";
    }
    cout << endl;
    
    return 0;
}

欧拉筛 vs 埃拉托斯特尼筛法

特性	欧拉筛	埃拉托斯特尼筛法
时间复杂度	O(n)	O(n log log n)
空间复杂度	O(n)	O(n)
重复标记	无	有
实现难度	稍难	简单

为什么欧拉筛是 O(n)？

关键在于内层循环的 if (i % p == 0) break;

假设 i = 12，primes = {2, 3, 5, 7, …}：

p = 2：12 × 2 = 24，标记为合数，12 % 2 == 0，停止
如果不停止，接着会用 p = 3 标记 36，但这步被跳过了

这样，每个合数 n 只会被其最小质因子 p 标记一次，总操作次数接近 n。

应用场景

质数筛取：快速生成大量质数
质因数分解：利用 SPF 快速分解任意数
数论问题：需要质数相关信息的场景

总结

欧拉筛是质数筛取的最优算法，虽然实现比传统筛法稍复杂，但 O(n) 的时间复杂度使其在处理大规模数据时具有明显优势。建议在实际应用中优先使用欧拉筛。