素数筛法详解：埃筛与欧拉筛原理与实现

1. 素数筛法基础概念

在计算机科学和数论中，素数筛法是一种用于快速生成素数列表的算法。最常见的两种筛法是埃拉托斯特尼筛法（埃筛）和欧拉筛法（线性筛）。这两种算法各有特点，适用于不同场景。

埃筛的时间复杂度是O(n log log n)，而欧拉筛可以达到O(n)。虽然埃筛不是线性的，但在实际应用中，由于其简单性和对小范围数据的高效性，仍然被广泛使用。

2. 埃拉托斯特尼筛法详解

2.1 算法原理

埃筛的基本思想是从小到大遍历所有数，当遇到一个素数时，将其所有倍数标记为合数。具体步骤如下：

1. 初始化一个布尔数组is_prime，长度为n+1，全部设为true
2. 将is_prime[0]和is_prime[1]设为false（0和1不是素数）
3. 从i=2开始遍历到n：
   • 如果is_prime[i]为true，则i是素数
   • 将i的所有倍数j（从i*i开始，步长为i）标记为false

2.2 代码实现

cpp复制vector<int> prime;
bool is_prime[N];

void Eratosthenes(int n) {
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; ++i) is_prime[i] = true;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            prime.push_back(i);
            if ((long long)i * i > n) continue;
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
}

2.3 优化技巧

1. 只筛到√n：因为任何合数n都至少有一个质因子不超过√n
2. 只考虑奇数：除了2，所有偶数都不是素数
3. 位压缩：使用位运算来减少内存占用

3. 欧拉筛法（线性筛）

3.1 算法原理

欧拉筛的关键在于确保每个合数只被其最小质因子筛掉一次。这通过以下方式实现：

1. 维护一个素数列表
2. 对于每个数i，用已知素数pri_j去筛i*pri_j
3. 当i能被pri_j整除时停止，保证每个数只被最小质因子筛掉

3.2 代码实现

cpp复制vector<int> pri;
bool not_prime[N];

void EulerSieve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!not_prime[i]) {