线性筛（欧拉筛）

线性筛（也称为欧拉筛）是一种高效的算法，用于筛选出小于等于某个整数 ( n ) 的所有质数，同时避免了传统埃拉托斯特尼筛法（埃氏筛）中重复筛选的问题。线性筛的时间复杂度为 ( O(n) )，因此在处理大规模数据时非常高效。

线性筛的基本原理

线性筛的核心思想是利用每个合数的最小质因数来筛选。每个合数只会被它的最小质因数筛掉一次，从而保证了每个数只被处理一次，达到线性时间复杂度。

以下是线性筛的基本步骤：

1. 初始化：
   创建一个布尔数组 is_prime，标记每个数是否为质数，初始时假设所有数都是质数（除了0和1）。
   创建一个数组 primes，用于存储找到的质数。

2. 遍历每个数：
   从2开始遍历到 ( n )。如果当前数 ( i ) 是质数，则将其加入质数数组 primes。

3. 筛选合数：
   对于每个质数 ( p )，在 ( p * i ) 的范围内，将 ( p * i ) 标记为合数。同时，如果 ( i ) 能被 ( p ) 整除，则停止当前质数的筛选，避免重复筛选。

4. 停止条件：
   当 ( i ) 能被某个质数 ( p ) 整除时，停止当前质数的筛选，因为后续的合数会被其他质数的倍数筛掉。

线性筛代码实现

以下是线性筛的C++代码实现：

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

vector<int> primes;  // 存储所有质数
bool is_prime[1000001];  // 标记是否为质数

void linearSieve(int n) {
    // 初始化
    for (int i = 0; i <= n; i++) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);  // 如果i是质数，加入质数列表
        }

        // 筛选合数
        for (int p : primes) {
            if (i * p > n) break;  // 超过范围，停止
            is_prime[i * p] = false;  // 标记i * p为合数

            // 如果i能被p整除，停止当前质数的筛选
            if (i % p == 0) break;
        }
    }
}

int main() {
    int n = 100;  // 示例：筛选1到100的质数
    linearSieve(n);

    // 输出所有质数
    for (int p : primes) {
        cout << p << " ";
    }
    return 0;
}

线性筛的关键点

1. 每个合数只被它的最小质因数筛掉一次：
   这是线性筛的核心特性，保证了时间复杂度为 ( O(n) )。

2. 停止条件：
   当 ( i ) 能被某个质数 ( p ) 整除时，停止当前质数的筛选。这是因为后续的合数会被其他质数的倍数筛掉。

3. 空间复杂度：
   线性筛需要一个布尔数组来标记质数，空间复杂度为 ( O(n) )。

线性筛的应用

线性筛不仅可以用于筛选质数，还可以用于其他数论问题，例如：

• 计算欧拉函数：通过线性筛同时计算每个数的欧拉函数值。
• 分解质因数：结合线性筛，快速分解质因数。

例题：洛谷的阶乘