素数筛：欧拉筛

欧拉筛是埃氏筛的优化版本，核心思想是每个合数只被它的最小质因子筛掉一次，从而实现真正的线性时间复杂度 O(n)。

基本原理

每个合数只会被它的最小质因子筛掉。

实现要点：

1. 维护一个素数列表 primes
2. 遍历每个数 i（从2到n）
3. 用当前素数列表中的素数 p 与 i 相乘，标记合数
4. 当 i % p == 0 时停止（保证最小质因子原则）

基础实现

const int N = 105;
bool isPrime[N] = {0, 0};
for (int i = 2; i < N; i++) isPrime[i] = true;
int primes[N], t = 0; // 质数表
    
for (int i = 2; i <= n; i++) {
    if (isPrime[i]) {
        primes[t++] = i;  // i是素数，加入列表
    }
    // 用当前素数去标记合数
    for (int p = 0; p < t && i * p <= n; p++) {
        isPrime[i * primes[p]] = false;  // 标记合数
        // 关键：如果p是i的最小质因子，停止
        if (i % primes[p] == 0) break;
    }
}

标准实现

vector<int> eulersieve(int n) {
    vector<bool> isPrime(n + 1, true);
    vector<int> primes;
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push_back(i);  // i是素数，加入列表
        }
        // 用当前素数去标记合数
        for (int p : primes) {
            if (i * p > n) break;  // 超出范围
            isPrime[i * p] = false;  // 标记合数
            // 关键：如果p是i的最小质因子，停止
            if (i % p == 0) break;
        }
    }
    return primes;
}
vector<int> primes = eulersieve(n);

时间复杂度与空间复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

应用场景

1. 快速分解质因数

2. 线性筛欧拉函数 φ(n)

3. 线性筛莫比乌斯函数 μ(n)

4. 线性筛约数个数 d(n)

埃氏筛 vs 欧拉筛

特性	埃氏筛	欧拉筛
时间复杂度	O(n log log n)	O(n)
常数因子	小	较大
空间复杂度	O(n)	O(n)
实现复杂度	简单	中等
实际速度（n≤1e7）	快	略快
实际速度（n≤1e8）	较慢	快
可扩展性	容易并行化	难以并行化
额外信息	仅素数判断	可获得最小质因子等

选择建议

1. n ≤ 10^7：两者差别不大，选埃氏筛（代码简单）
2. n > 10^7：选欧拉筛（真正的线性）
3. 需要最小质因子：必须用欧拉筛
4. 需要筛积性函数（欧拉函数、莫比乌斯函数等）：必须用欧拉筛
5. 内存受限：埃氏筛可用 bitset 优化