筛法

---

🧮 埃式筛法

原理简介

对每个大于 $1$ 的整数 $n$，其大于自身的倍数一定是合数。基于此性质：

• 从 $2$ 开始枚举每个数 $i$，若 $i$ 没有被标记为合数，则为质数。
• 将 $i$ 的所有倍数标记为合数。
• 重复此过程直到上限 $n$。

基本实现

bool vis[1000005]; // 标记数组，false 表示是质数
void prime(int n) 
{
    vis[0] = vis[1] = true; // 0 和 1 不是质数
    for (int i = 2; i <= n; i++) 
    {
        if (!vis[i]) 
        {
            for (int j = i * 2; j <= n; j += i)
                vis[j] = true;
        }
    }
}

埃式筛法为何重复标记多次？

因为一个合数 $j$ 可能有多个质因子，显然每个质因子的若干倍都会将 $j$ 标记一次。

优化实现

• 内层循环从 $i \times i$ 开始，避免重复标记：、
  • 对于时间复杂度没有提升。

bool vis[1000005];
void prime(int n) 
{
    vis[0] = vis[1] = true;
    for (int i = 2; i * i <= n; i++) 
    {
        if (!vis[i]) 
        {
            for (int j = i * i; j <= n; j += i)
                vis[j] = true;
        }
    }
}

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

调和级数分析示例：

形如这样的代码，其时间复杂度都是调和级数级别的。

for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i)

此类嵌套循环执行次数约为：

\[ T(n) = n \left( \frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{n} \right) = O(n\log n) \]

---

🚀 欧拉筛法

核心思想

改进埃式筛中 一个合数可能被多个质因子标记 的问题，确保每个合数只被其 最小质因子 筛一次。

优势

• 每个合数只被唯一一次标记，时间复杂度为 $O(n)$。

实现代码

const int N = 1000005;
bool vis[N]; // 合数标记
int p[N], cnt = 0; // 存质数

void prime(int n) 
{
    vis[0] = vis[1] = true;
    for (int i = 2; i <= n; i++) 
    {
        if (!vis[i]) p[++cnt] = i; // i 是质数
        for (int j = 1; j <= cnt && i * p[j] <= n; j++)
        {
            vis[i * p[j]] = true;
            if (i % p[j] == 0) break; // 保证最小质因子唯一
        }
    }
}

原理解释

• 每个数 $i$ 遍历所有小于等于 $i$ 的质数 $p_j$。
• 若 $i \equiv 0\bmod p_j$，说明 $p_j$ 是 $i$ 的最小质因子，则 $i \times p_j$ 同样最小质因子为 $p_j$，之后的倍数交由更大数处理。

扩展：记录每个数的最小质因子

int f[N]; // f[i] 表示 i 的最小质因子
void prime(int n) 
{
    vis[0] = vis[1] = true;
    for (int i = 2; i <= n; i++) 
    {
        if (!vis[i]) 
        {
            p[++cnt] = i;
            f[i] = i;
        }
        for (int j = 1; j <= cnt && i * p[j] <= n; j++) 
        {
            vis[i * p[j]] = true;
            f[i * p[j]] = p[j];
            if (i % p[j] == 0) break;
        }
    }
}

应用场景

• 快速判定素数
• 获取 $[1, n]$ 中所有素数
• 快速质因数分解
• 使用 bitset 结合埃式筛法性能甚至快过欧拉筛。

---

📘 延伸阅读：

• 质数分布定理：$\pi(n) \sim n/\ln n$，意思是：$[1,n]$ 以内的质数个数大约是 $\frac{n}{\ln n}$。

补充一：预处理最大质因子

利用埃式筛的过程，同时维护每个数字的最大质因子：

int mx[N];
bool vis[N];
for (int i = 2; i <= n; i++)
{
    if (!vis[i])
    {
        mx[i] = i;
        for (int j = i * 2; j <= n; j += i)
        {
            vis[j] = 1;
            mx[j] = i; // 最大质因子更新为 i
        }
    }
}

---

补充二：预处理所有因子 / 因子个数 / 因子和

思想：枚举每个数 $i$，然后枚举它的倍数 $j$，则 $i$ 一定是 $j$ 的因子。

vector<int> fact[N];
vector<int> f(n + 1), g(n + 1); // f[i]: 因子个数, g[i]: 因子和
for (int i = 1; i <= n; i++)
{
    for (int j = i; j <= n; j += i)
    {
        f[j]++;
        g[j] += i;
        fact[j].push_back(i);
    }
}

---

补充三：区间筛法

场景

当筛选的区间范围是 $[L, R]$，且 $R$ 很大（如 $10^{12}$）时，普通筛法无法直接使用。此时用区间筛。

原理

• 先用埃式筛预处理 $[2, \sqrt{R}]$ 范围内的质数存储到 vector<int> primes；
• 创建一个 $R - L + 1$ 大小的布尔数组标记区间 $[L, R]$；
• 枚举每个小质数 $p$，用它标记 $[L, R]$ 中的所有倍数。
  • 解释：$[L,R]$ 内的合数，其最小质因子必然 $\leq \sqrt{R}$。因此用这些质数 $p$ 可以标记完 $[L, R]$ 中的所有合数。

标记大区间的具体实现

• 枚举每个小质数 $p$。for (auto p : primes)
  • 接下来就是在区间 $[L, R]$ 内找到第一个 $p$ 的倍数记作 start。
  • 从 start 开始遍历到 $R$，标记所有 $p$ 的倍数。
  • 因此重点是如何求出 区间 $[L, R]$ 内找到第一个 $p$ 的倍数 start。

假设 $p\cdot x\geq L$，现在就是求出刚好满足该不等式的 $x$，容易解得 $x\geq \frac{L}{p}$。由于 $x$ 为整数，因此 $x$ 取 $\lceil\dfrac{L}{p} \rceil$。

注意 $x$ 可能等于 $1$ 导致标记了 $p$ 自己，因此 $x$ 需要和 $2$ 取 $\max$。

// 埃式筛预处理 sqrt(R) 以内的质数
int lim = sqrt(R);
vector<bool> vis(lim + 1, false);
for (int i = 2; i <= lim; i++)
{
    if (!vis[i])
    {
        for (int j = i * 2; j <= lim; j += i)
            vis[j] = true;
    }
}
vector<int> primes;
for (int i = 2; i <= lim; i++)
    if (!vis[i])
        primes.push_back(i);


// 标记区间 [L, R] 中合数
vector<bool> isprime(R - L + 1, false);
for (int p : primes)
{
    long long x = max(2, (L + p - 1) / p); // p * x >= L
    long long start = p * x;
    for (long long j = start; j <= R; j += p)
        isprime[j - L] = true;
}
// 特殊处理 1
if (L == 1) isprime[0] = true;
// 输出所有质数
for (int i = 0; i <= R - L; i++)
{
    if (!isprime[i])
    {
        cout << i + L << "\n";
    }
}

时间复杂度

$O(\sqrt{R} + (R-L+1) \log\log R)$，空间复杂度 $O(R-L+1)$

适合 $R-L \leq 10^6$，但 $R$ 本身很大（如 $10^{12}$）的情况。

---

总结

方法	时间复杂度	空间	特点
埃式筛	$O(n\log\log n)$	$O(n)$	结构简单，适用于 $n \leq 10^7$
欧拉筛	$O(n)$	$O(n)$	每个合数只被最小质因子筛一次
区间筛	$O(\sqrt{R} + (R-L+1))$	$O(R-L+1)$	适合 $R$ 很大，$R-L$ 小