筛 (sieve) 是通过逐步去除不满足条件的元素，从而剩下满足条件的元素的一种方法。应用于质数时，质数筛是滤去不超过给定正整数 N 的合数，从而筛出 [2, N] 中全体质数的方法。

经典筛法

Eratosthenes 筛

Eratosthenes 筛是一种经典的算法，能以 O(n \log \log n) 的复杂度筛出区间 [2, N] 的全体质数。

性质

每个合数会被所有质因数筛过一次。即，设 a \notin \mathbb{P} ，且 a = \prod \limits_{i = 1}^n p_i^{\alpha_i} ，其中 p_i \in \mathbb{P}, \alpha_i > 0 ，则 a 会被 p_1, p_2, \dots, p_n 都筛过一遍。

利用这一点，也可以借助 Eratosthenes 获得一个数最大的质因数。

Euler 筛（线性筛）

Euler 筛以 O(n) 的复杂度筛出 [2, N] 的全体质数。该方法对于每个合数都只用一个质数筛去，不会出现一个质数重复多次筛去合数的情形。

代码

const size_t MAXN = 100000; // 最大数量

unsigned primes[MAXN];
bool is_prime[MAXN];

size_t euler_sieve(unsigned n) // 最大筛到几
{
    memset(is_prime + 1, 1, n * sizeof(bool));
    is_prime[0] = is_prime[1] = false;
    size_t cnt = 0;
    for (unsigned i = 2; i <= n; i++)
    {
        if (is_prime[i])
        {
            primes[cnt++] = i;
        }
        for (size_t j = 0; j < cnt; j++)
        {
		    if ((long long) i * primes[j] > n) break;
		    is_prime[i * primes[j]] = false;
		    if (i % primes[j] == 0) break;
        }
    }
    return cnt;
}

证明

参考：欧拉筛详解 - CSDN

假设我们尝试通过 Euler 筛筛去合数 a ，设其最小质因数为 p_1 ，a = p_1 b ，则显然 b < a ，在外层循环 for (size_t i = 2; i <= n; i++) 中 b 先于 a 出现。

正确性：下面证明 b 将在内层循环中筛去 a 。由于 p_1 是 a 的最小质因数，b 的最小质因数 p_2 必定大于等于 p_1 ，故在内层循环中，遍历了所有小于 p_2 的质数 p （自然包括 p_1），在 b 满足判断 if (i % primes[j] == 0) 即 p = p_2 导致 break 之前，必定已经筛掉了 a .

唯一性：再证明 a 只会被筛一次。假设 a 除了被 b 以外，还被 c 筛去了，设 a = p_3 c ，则在外层循环 i = c 时，c 将通过内层循环筛去 a 。因为 p_1 是 a 最小的质因数，故必定有 p_3 \ge p_1 ，则 c \le b ，但 c \ne b ，故 c < b ，则 p_3 > p_1 。这意味着 p_1 是 c 的质因数，则在 i = c 时的内层循环中，当 primes[j] 等于 p_1 时就因为判断 i % primes[j] == 0 成立而 break 了，不可能取到 p_3 ，也就不可能通过 is_prime[i * primes[j]] = false 筛掉 a ，矛盾。

性质

时间复杂度为 O(n) ，因为每个合数只被筛掉一次。

空间复杂度为 O(n) 。

合数被最小质因数筛去

每个合数都会由最小的质因数筛去（即，代码中 is_prime[i * primes[j]] = false 中的 primes[j] 为该合数的最小因数）。据此可以用筛法计算 Euler 函数值。

筛法的应用

Euler 筛法求 Euler 函数

Euler 函数是积性函数：若 m, n 互质（即 (m, n) = 1 ），则 \varphi(m n) = \varphi(m) \varphi(n) 。

应用 Euler 筛法时，每个合数 a 都被最小质因数 p 筛去，设 a = pb ，则可以分 p \mid b 和 p \nmid b 讨论。

当 p \nmid b 时，有 (p, b) = 1 （依据整数环），于是 \varphi(a) = \varphi(p) \varphi(b) = (p - 1)\varphi(b) （依据（链接未公开））；
当 p \mid b 时，设 a 的全体质因数为 p = p_1, \dots, p_n ，则 p_1, \dots, p_n 也是 b 的全体质因数。由（链接未公开），有$$ \varphi(a) = a\prod_{k=1}^n \frac{p_k - 1}{p_k} = p b \prod_{k=1}^n \frac{p_k - 1}{p_k} = p \varphi(b).

归纳以上两者情况，有

\varphi(a) = \begin{cases} &(p - 1) \varphi(b), & p \nmid b; \ & p \varphi(b), & p \mid b. \end{cases}

$而质数p的 Euler 函数值为p - 1（（链接未公开）），且应用 Euler 筛法时，由于b < a，b先于a$ 被取出。故由数学归纳原理，Euler 函数值可以通过 Euler 筛法计算。

筛法求因子个数

Euler 筛法求因数和

原理

CSDN

依然利用“积性”和递推方法。

设数列 s[a] 表示数 a 的因数和。对于质数 p，有 s[p] = 1 + p （（链接未公开））。对于合数 a ，设 p_1 是 a 的最小质因数， a = p_1b 。当 p_1 \nmid b 时，有 (p_1, b) = 1 （整数环），由（链接未公开）， s[a] = s[b] s[p_1] = s[b] (1 + p_1) 。当 p_1 \mid b 时，设 b = \prod\limits_{k = 1}^n p_k^{\alpha_k} ，则 a = p_1^{\alpha_1 + 1} \prod\limits_{k = 2}^n p_k^{\alpha_k} 。由（链接未公开）可知，b 的全体因数和为：

s[b] = (1 + p_1 + \cdots + p_1^{\alpha_1}) \prod_{k=2}^n (1 + p_k + \cdots + p_k^{\alpha_k});

而 a 的全体正因数和为：

s[a] = (1 + p_1 + \cdots + p_1^{\alpha_1 + 1}) \prod_{k=2}^n (1 + p_k + \cdots + p_k^{\alpha_k});

对比两式，得到：

s[a] = s[b] \cdot \frac{(1 + p_1 + \cdots + p_1^{\alpha_1 + 1})}{(1 + p_1 + \cdots + p_1^{\alpha_1})} = s[b] \cdot \frac{p_1^{\alpha_1 + 2} - 1}{p_1^{\alpha_1 + 1} - 1}.

于是，可以使用递推方法计算因数和。

代码

以下代码中，因子和储存在 factor_sum 中。

const size_t MAXN = 1000000;
typedef unsigned long long ull;

ull factor_sum[MAXN + 5];
bool is_prime[MAXN + 5];
ull primes[MAXN + 5];
size_t min_prime_index[MAXN + 5];
ull min_prime_pow[MAXN + 5];

void factor_sum(size_t n)
{
    memset(is_prime + 1, 1, n);
    is_prime[0] = is_prime[1] = false;
    size_t cnt = 0;
    for (size_t i = 2; i <= n; i++)
    {
        if (is_prime[i])
        {
            primes[cnt++] = i;
            factor_sum[i] = i + 1;
            min_prime_pow[i] = i * i;
            min_prime_index[i] = 1;
        }
        for (size_t j = 0; j < cnt; j++)
        {
            ull a = i * primes[j];
            if (a > MAXN) break;
            is_prime[a] = false;
            if (i % primes[j] != 0)
            {
                min_prime_index[a] = 1;
                min_prime_pow[a] = primes[j] * primes[j];
                factor_sum[a] = (1 + primes[j]) * factor_sum[i];  
            }
            else
            {
                min_prime_index[a] = min_prime_index[i] + 1;
                min_prime_pow[a] = min_prime_pow[i] * primes[j];
                factor_sum[a] = factor_sum[i] * \
                    (min_prime_pow[a] - 1) / (min_prime_pow[i] - 1);
                break;
            }
        }
    }
}

一般的积性函数

如果 f(p^k) 的值可以在 O(1) 内求出，则可以用筛法求积性函数在 [1, n] 的取值，时间复杂度是 O(n)。