一、 埃氏筛 (Sieve of Eratosthenes)

这是最基础、最符合直觉的筛法。

• 算法流程：

1. 假设所有数都是质数。
2. 从 2 开始从小到大遍历，如果遇到一个质数 $i$，就把它的所有倍数（$i \times i, i \times (i+1) \dots$）全都标记为合数。

• 适用场景：

• 求 $1 \sim N$ 的质数（但速度不如线性筛）。

• 核心特长：由于它是枚举质数的倍数，所以非常适合在筛的过程中，顺便求出每个数的所有质因子，或者处理某些非积性函数。

• 时间复杂度：$O(N \log \log N)$

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1000005;
bool is_prime[N];
int primes[N], cnt;

void eratosthenes(int n) {
    // 1. 初始化全为质数
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = is_prime[1] = 0;
    
    // 2. 从 2 开始遍历
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes[cnt++] = i; // 记录质数
            // 3. 将 i 的倍数标记为合数，从 i*i 开始优化（因为更小的倍数已被更小的质数筛去）
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = 0;
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    eratosthenes(100);
    return 0;
}

二、 线性筛 / 欧拉筛 (Euler's Sieve)

竞赛绝对主力，也是你必须肌肉记忆的模板。

• 算法流程：

1. 假设所有数都是质数。
2. 遍历 $2 \sim N$：如果是质数，加入质数表。
3. 遍历已知质数表，将 当前数 * 质数 标记为合数。
4. 灵魂一步：如果当前数能被该质数整除，立刻 break。保证每个合数只被它的最小质因数筛掉一次。

• 适用场景：

• 快速求 $1 \sim N$ 的所有质数。

• 核心特长：结合 break 的性质，极其适合线性求各种积性函数（如欧拉函数 $\phi$、莫比乌斯函数 $\mu$、约数个数等）。

• 时间复杂度：绝对严格的 $O(N)$

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1000005;
bool is_prime[N];
int primes[N], cnt;

void linear_sieve(int n) {
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = is_prime[1] = 0;
    
    for (int i = 2; i <= n; i++) {
        // 发现质数
        if (is_prime[i]) primes[cnt++] = i;
        
        // 遍历已知质数
        for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
            is_prime[i * primes[j]] = 0; // 筛掉合数
            
            // 遇到最小质因数，立刻停止，防止重复筛选
            if (i % primes[j] == 0) break;
        }
    }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    linear_sieve(100);
    return 0;
}

根据数论基础：如果一个数 $X \le U$ 是合数，那么它必定有一个质因数 $P \le \sqrt{U}$。 因为 $\sqrt{2^{31}-1} \approx 46340$，所以我们只需要： 第一步（预处理）：用线性筛求出 $1 \sim 50000$ 范围内的所有质数。 第二步（区间筛）：对于每组输入的 $L$ 和 $U$，遍历我们预处理出的质数 $P$。算出在 $[L, U]$ 区间内 $P$ 的倍数，把它们全部标记为合数。为了不爆内存，我们将下标平移，用 is_p[i - L] 来代表数字 i 是否为合数。 第三步（统计）：遍历平移后的标记数组，记录相邻两个质数的差值，不断更新最大值和最小值即可。