线性筛法 (Linear Sieve) 模板详解

线性筛法 (Linear Sieve) 模板详解

1. 简介

线性筛法（也称欧拉筛法）是一种高效的素数筛选算法，它不仅可以在线性时间内筛出素数，还能同时得到每个数的最小质因子。

主要特点：

  • 线性时间复杂度 O(n)
  • 可以获得最小质因子
  • 避免重复筛选
  • 可以扩展求解积性函数

2. 实现原理

2.1 基本概念

  1. 素数：

    • 只能被1和自身整除的大于1的整数
    • 2是最小的素数

  2. 最小质因子：

    • 一个合数的最小素数因子
    • 对素数来说，最小质因子是其自身

2.2 核心策略

  1. 筛选过程：

    • 用已知的素数去筛选更大的数
    • 每个合数只被其最小质因子筛掉一次

  2. 优化方法：

    • 维护最小质因子数组
    • 按照特定顺序筛选，避免重复

3. 模板代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
std::vector<int> minp, primes;

void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();
    
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        
        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                break;
            }
        }
    }
}

4. 函数说明

4.1 参数说明

1
void sieve(int n)
  • n: 要筛选的范围上限
  • minp: 存储每个数的最小质因子
  • primes: 存储筛选出的所有素数

4.2 返回值

  • 函数无返回值
  • 通过全局变量 minp 和 primes 返回结果

5. 时间复杂度分析

  • 时间复杂度：O(n)

    • 每个合数只被其最小质因子筛掉一次
    • 内层循环的总执行次数是线性的

  • 空间复杂度：O(n)

    • minp 数组需要 O(n) 空间
    • primes 数组需要 O(n/ln(n)) 空间

6. 应用场景

  1. 生成素数表
  2. 判断素数
  3. 质因数分解
  4. 求解积性函数
  5. 数论相关问题

7. 使用示例

7.1 生成素数表

1
2
3
4
5
sieve(100);
// primes 中存储了 100 以内的所有素数
for (int p : primes) {
    cout << p << " ";  // 2 3 5 7 11 13 17 19 23 29 ...
}

7.2 判断素数

1
2
3
4
sieve(n);
bool isPrime(int x) {
    return x > 1 && minp[x] == x;
}

7.3 质因数分解

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<pair<int, int>> factorize(int x) {
    vector<pair<int, int>> res;
    while (x > 1) {
        int p = minp[x];
        int cnt = 0;
        while (x % p == 0) {
            x /= p;
            cnt++;
        }
        res.emplace_back(p, cnt);
    }
    return res;
}

8. 注意事项

  1. 内存限制

    • 注意数组大小不要超过内存限制
    • 对于大范围可以分段筛选

  2. 初始化

    • 使用前需要调用 sieve 函数
    • 确保范围 n 足够大

  3. 特殊情况

    • 注意处理 n = 1 的情况
    • 考虑数组访问边界

9. 总结

线性筛法是一个高效的素数筛选算法，它不仅可以在线性时间内找出所有素数，还能得到每个数的最小质因子。这个算法在很多数论问题中都有重要应用，特别是在需要进行大量质因数分解的场景下。通过合理的实现和优化，可以在实际应用中获得很好的性能。