一、算法概述

筛法（Sieve）是一种用于高效筛选 [1, n] 范围内所有质数（素数）的经典算法。主要有两种实现：

• 埃拉托斯特尼筛法（埃氏筛，Sieve of Eratosthenes）：简单直观，时间复杂度 O(n log log n)。
• 欧拉筛 / 线性筛（Euler's Sieve / Linear Sieve）：更精妙，时间复杂度 O(n)，每个合数只被其最小质因子筛掉一次。

---

二、核心思想

埃氏筛

• 从小到大遍历每个数 i（2 到 √n）。
• 若 i 是质数（未被标记为合数），则将 i 的所有倍数（2i, 3i, 4i...）标记为合数。
• 遍历结束后，未被标记的数即为质数。

欧拉筛（线性筛）

• 维护一个质数列表 primes，以及标记数组 isComposite。
• 从小到大遍历每个数 i（2 到 n）：
  • 若 i 未被标记，将 i 加入质数列表。
  • 对于质数列表中的每个质数 p（直到 i * p > n）：
    • 标记 i * p 为合数。
    • 若 i % p == 0，则停止（保证每个合数只被其最小质因子筛掉）。
• 关键：i % p == 0 时 break，使得每个合数 x 只会被 x / minPrimeFactor(x) 这个数筛掉，确保线性时间。

---

三、算法步骤 / 伪代码

埃氏筛(n)：
1. isPrime[0..n] 初始化为 true，isPrime[0]=isPrime[1]=false
2. for i = 2 to sqrt(n)：
     if isPrime[i]：
       for j = i*i to n step i：
         isPrime[j] = false
3. 收集 isPrime[i]==true 的 i 即为质数列表

欧拉筛(n)：
1. primes = []，isComposite[0..n] 初始化为 false
2. for i = 2 to n：
     if not isComposite[i]：primes.push(i)
     for each p in primes：
       if i * p > n：break
       isComposite[i * p] = true
       if i % p == 0：break     // 关键！保证线性
3. primes 即为质数列表

---

四、C++ 代码实现

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

// ==================== 埃氏筛 ====================
class EratosthenesSieve {
public:
    // 返回 [2, n] 内的所有质数
    vector<int> getPrimes(int n) {
        if (n < 2) return {};
        vector<bool> isPrime(n + 1, true);
        isPrime[0] = isPrime[1] = false;

        // 只需筛到 sqrt(n)
        int limit = (int)sqrt(n);
        for (int i = 2; i <= limit; i++) {
            if (isPrime[i]) {
                // 从 i*i 开始，因为 2i, 3i, ..., (i-1)*i 已被更小的质数筛过
                for (long long j = (long long)i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        vector<int> primes;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) primes.push_back(i);
        }
        return primes;
    }

    // 返回 [2, n] 内质数的个数
    int countPrimes(int n) {
        return (int)getPrimes(n).size();
    }
};

// ==================== 欧拉筛（线性筛） ====================
class EulerSieve {
public:
    // 返回 [2, n] 内的所有质数
    vector<int> getPrimes(int n) {
        if (n < 2) return {};
        vector<bool> isComposite(n + 1, false);  // 是否为合数
        vector<int> primes;                       // 质数列表

        for (int i = 2; i <= n; i++) {
            // 当前数 i 未被筛掉，则为质数
            if (!isComposite[i]) {
                primes.push_back(i);
            }

            // 用已找到的质数去筛 i * p
            for (int p : primes) {
                long long multiple = (long long)i * p;
                if (multiple > n) break;

                isComposite[multiple] = true;

                // ★ 核心：当 p 是 i 的因子时，停止筛选
                // 保证每个合数只被其最小质因子筛掉
                if (i % p == 0) break;
            }
        }
        return primes;
    }

    int countPrimes(int n) {
        return (int)getPrimes(n).size();
    }
};

// ==================== 质因数分解（利用欧拉筛预处理的 minPrime） ====================
class PrimeFactorization {
private:
    vector<int> minPrime;  // minPrime[x] 表示 x 的最小质因子（欧拉筛副产品）

public:
    // 预处理 [2, n] 每个数的最小质因子
    void build(int n) {
        minPrime.assign(n + 1, 0);
        vector<int> primes;
        for (int i = 2; i <= n; i++) {
            if (minPrime[i] == 0) {
                minPrime[i] = i;  // 质数的最小质因子就是它本身
                primes.push_back(i);
            }
            for (int p : primes) {
                long long multiple = (long long)i * p;
                if (multiple > n) break;
                minPrime[multiple] = p;
                if (i % p == 0) break;
            }
        }
    }

    // 对 x 进行质因数分解，返回 {质因子, 指数} 列表
    vector<pair<int, int>> factorize(int x) {
        vector<pair<int, int>> result;
        while (x > 1) {
            int p = minPrime[x];
            int cnt = 0;
            while (x % p == 0) {
                x /= p;
                cnt++;
            }
            result.push_back({p, cnt});
        }
        return result;
    }

    // 分解并打印
    void printFactorization(int x) {
        auto fac = factorize(x);
        cout << x << " = ";
        for (int i = 0; i < (int)fac.size(); i++) {
            if (i > 0) cout << " * ";
            cout << fac[i].first << "^" << fac[i].second;
        }
        cout << endl;
    }
};

// ==================== 测试用例 ====================
int main() {
    cout << "========== 埃氏筛 ==========" << endl;
    EratosthenesSieve es;
    int n = 100;
    vector<int> primes1 = es.getPrimes(n);
    cout << "1 ~ " << n << " 内的质数 (" << primes1.size() << " 个):" << endl;
    for (int i = 0; i < (int)primes1.size(); i++) {
        cout << primes1[i] << (i + 1 == (int)primes1.size() ? "" : ", ");
        if ((i + 1) % 10 == 0) cout << endl;
    }
    cout << endl << endl;

    cout << "========== 欧拉筛（线性筛） ==========" << endl;
    EulerSieve ls;
    vector<int> primes2 = ls.getPrimes(100);
    cout << "1 ~ 100 内的质数 (" << primes2.size() << " 个):" << endl;
    for (int i = 0; i < (int)primes2.size(); i++) {
        cout << primes2[i] << (i + 1 == (int)primes2.size() ? "" : ", ");
        if ((i + 1) % 10 == 0) cout << endl;
    }
    cout << endl << endl;

    // LeetCode 204: 计数质数
    cout << "========== LeetCode 204: 计数质数 ==========" << endl;
    cout << "n = 10, 质数个数 = " << es.countPrimes(10) << " (答案: 4)" << endl;
    cout << "n = 0,  质数个数 = " << es.countPrimes(0)  << " (答案: 0)" << endl;
    cout << "n = 1,  质数个数 = " << es.countPrimes(1)  << " (答案: 0)" << endl;
    cout << "n = 2,  质数个数 = " << es.countPrimes(2)  << " (答案: 0)" << endl;

    cout << endl;
    cout << "========== 质因数分解 ==========" << endl;
    PrimeFactorization pf;
    pf.build(100);
    pf.printFactorization(12);
    pf.printFactorization(36);
    pf.printFactorization(97);
    pf.printFactorization(100);
    pf.printFactorization(84);

    return 0;
}

---

五、复杂度分析

筛法类型	时间复杂度	空间复杂度	说明
埃氏筛	O(n log log n)	O(n)	每个质数 p 筛 n/p 个倍数，调和级数求和得到 n log log n。常数很小，实践中非常快。
欧拉筛	O(n)		每个合数恰好被筛一次（被其最小质因子筛掉），严格线性。常数比埃氏筛略大，但理论上最优。

---

六、应用场景

1. 质数筛选：获取某范围内的所有质数（如 LeetCode 204 计数质数）。
2. 质因数分解：通过预处理最小质因子实现 O(log n) 分解（见代码中 PrimeFactorization 类）。
3. 欧拉函数 φ(n) 批量计算：线性筛可同时求出 1 ~ n 的欧拉函数值。
4. 莫比乌斯函数 μ(n) 批量计算：同样是线性筛的副产品。
5. 预处理质数表：作为许多数论问题（如质数判定、筛法求积性函数）的基础。
6. 密码学：RSA 等算法需要大质数生成和判定，筛法用于生成小质数表辅助 Miller-Rabin 检测。

---

七、经典例题

LeetCode 204. 计数质数

题目描述：给定整数 n，返回所有小于非负整数 n 的质数的数量。

示例：

• 输入: n = 10，输出: 4（质数有 2, 3, 5, 7）
• 输入: n = 0，输出: 0
• 输入: n = 1，输出: 0

解法说明：使用埃氏筛或欧拉筛，筛选出 [2, n-1] 区间内的所有质数，返回质数个数即可。上述 C++ 代码中的 countPrimes 方法已实现该功能。

---

说明：以上 C++ 代码完整可编译，使用 g++ -std=c++17 -O2 filename.cpp -o main 编译后直接运行即可看到所有测试用例的输出。