数论基础之筛法

目录
  1. 1. 筛素数的算法
    1. 1.1. 朴素筛法
    2. 1.2. 线性筛
    3. 1.3. 程序实现
  2. 2. 欧拉函数的筛法
    1. 2.1. 欧拉函数
    2. 2.2. 朴素筛法
      1. 2.2.1. 程序实现
    3. 2.3. 线性筛
      1. 2.3.1. 程序实现
  3. 3. 练习

筛素数的算法

朴素筛法

朴素的筛素数算法的流程是这样的：

  1. $i$ 没有被标记，$i$ 是素数；用 $i$ 去标记所有的 $i,2i,\cdots,\left\lfloor \frac{N}{i} \right\rfloor \times i$
  2. $i$ 被标记，$i$ 不是素数

这个算法的复杂度好像是 $O(N\log N)$ 的，其中，$N$ 为要筛的数的个数。
一个简单的优化技巧是：如果 $i$ 是素数，则用 $i$ 去标记所有的 $i^2,(i+1)\times i,\cdots,\left\lfloor \frac{N}{i} \right\rfloor \times i$。

优化之后的复杂度好像是 $O\big(N\log (\log N)\big)$ 的。
之所以强调好像是，是因为这两个复杂度都是道听途说的，未能严谨证明。
但是，显然它们都不会是线性的。比如 $12$，会被 $2,3$ 各标记一次。

线性筛

对于任意一个大于 1 的整数 $X$，可以将其写为 $X=e\cdot X’$。
其中，$e$ 是 $X$ 的最小正素因子。特别地，如果 $X$ 是一个素数，有 $X=e$。
那么，如果能让每一个正整数 $X$ 仅被其最小正素因子标记，就可以保证筛法的复杂度是线性的了。

先看怎么实现，再解释为什么是线性的。

程序实现

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef long long LL;
bool isprime[MAXN];
int prime[MAXN], tot; // 一般来说，素数个数在 MAXN/10 ～ MAXN/15 左右 

void GetPrime() {
    memset(isprime, 1, sizeof isprime); // 需要头文件 cstring
    tot = 0;
    for(int x=2; x < MAXN; ++x) {
        if( isprime[x] ) prime[tot++] = x;
        for(int i=0; i < tot; ++i) {
            if( (LL) prime[i]*x >= MAXN ) break; // 注意乘法溢出
            isprime[prime[i]*x] = false;
            if( x % prime[i] == 0 ) break; // 保证每个数仅被其最小正素因子标记
        }
    }
}

先考虑上述筛法的正确性。

如果 $X$ 是一个合数，令 $X=e\cdot X’$，其中 $e$ 为 $X$ 的最小正素因子。
首先，$e <= X’$，所以当 $x=X’$ 时，$e$ 已经在 prime 中了。
其次，不存在一个正素数 $e’ < e$ 满足 $e’ \mid X’$；因为如果存在这样的 $e’$，
则 $X=e’\cdot\frac{X’}{e’}\cdot e$，与 $e$ 是 $X$ 的最小素因子矛盾。

也就说，如果 $X$ 是一个合数，那么必会执行（我们已经排除了所有跳过的可能） $ isprime[e*X’] = false$ ，
所以这个筛法可以无疑漏的标记所有的合数。
又因为 $prime[i]*x$ 是一个合数，所以这个筛法不会标记素数。
据此，证明了该筛法的正确性。

再考虑上述筛法的效率。

  1. 如果 $X=e^k$，那么显然不用担心它被多个不同的素数筛过。
  2. 如果 $X=e_1*e_2*X’$，其中 $e_1 < e_2$；
    令 $x_2=\frac{X}{e_2}$，显然，$e_1 \mid x_2$，对应程序中，即会触发第 13 行操作： 
    1
    if( x2 % e1 == 0 ) break;
    而 $e_2 > e_1$，也就是说， $x_2$ 在遇见 $e_1$ 时就会结束内层循环，不会遇见 $e_2$，
    所以保证了 $X$ 至多仅被 $e_1$ 筛一次。

综上，此筛法是 $O(N)$ 的。

欧拉函数的筛法

欧拉函数

欧拉函数 $\varphi(X)$ 表示 $1,2,\cdots,X-1$ 中与 $X$ 互质的数的个数。

定义函数： $\hskip 2em f(x,y) = \left\lbrace \begin{aligned}
&1, &\gcd(x,y)=1 \
&0, &\gcd(x,y) \neq 1
\end{aligned} \right.$
对于正整数 $X$，那么，
$$\varphi(X)=\sum_{i=1}^{X-1} f(X,i). \tag{1}$$
更一般地，将 $X$ 唯一分解，得：$X=p_1^{k_1}\cdot p_2^{k_2}\cdots p_s^{k_s}$。
那么，
$$\varphi(X)=X\cdot \left(1-\frac{1}{p_1}\right) \cdot \left(1-\frac{1}{p_2}\right) \cdots \left(1-\frac{1}{p_s}\right). \tag{2}$$

下面利用容斥原理简单证明一下 **方程(2)**：
【证明】
$\hskip 2em$ 将 $X$ 唯一分解，得：$X=p_1^{k_1}\cdot p_2^{k_2}\cdots p_s^{k_s}$。
$\hskip 2em$ 令 $A_i$ 为比 $X$ 小且被 $p_i$ 整除的正整数集合。
\begin{align}
\varphi(X)
&= X-\sum_{i=1}^s \big|A_i\big|+\sum_{i=1}^s \sum_{j > i} \big|A_i \bigcap A_j\big|-\sum_{i=1}^s\sum_{j > i}\sum_{k > j} \big| A_i \bigcap A_j \bigcap A_k \big|+\cdots \
&~~~ +(-1)^{s}\big|A_1\bigcap A_2\bigcap \cdots \bigcap A_s \big| \
&= X-\sum_{i=1}^s \frac{X}{p_1}+\sum_{i=1}^s\sum_{j > i} \frac{X}{p_ip_j}-\sum_{i=1}^s\sum_{j > i}\sum_{k > j} \frac{X}{p_ip_jp_k}+\cdots+(-1)^s\frac{X}{p_1p_2\cdots p_s} \
&= X\cdot \left(1-\frac{1}{p_1}\right) \cdot \left(1-\frac{1}{p_2}\right) \cdots \left(1-\frac{1}{p_s}\right)
\end{align}
【证毕】

朴素筛法

方程(2) 虽然给出了欧拉函数的一个简单计算方法，但是，
注意到质因数分解的复杂度是 $O(\sqrt{N})$ 的，如果多次这样计算代价太大。
考虑筛除所有的素数，并用每个素数更新 $\varphi(X)$ 的值。

程序实现

朴素筛

1
2
3
4
5
6
7
8
9
10
11
12
typedef long long LL;
int phi[N];
void GetPhi() {
    memset(phi, 0, sizeof phi);
    phi[1] = 1;
    for(int i=2; i < N; ++i) if( !phi[i] ) {
        for(int j=i; j < N; j += i) {
            if( !phi[j] ) phi[j] = j;    
            phi[j] = phi[i] / i * (i-1); // 先除后乘防止溢出
        }
    }
}

这个程序可以生成 $X \in [1,N)$ 的欧拉函数表，且时间复杂度与朴素筛素数方法同阶，据说是 $O(N\log(N))$ 的。

线性筛

基于素数线性筛的思想，不妨设 $X=e\cdot X’$，其中，$e$ 为 $X$ 的最小素因子。

  1. 当 $e \mid X’$ 时，由上述计算公式可知，$\varphi(X) = \varphi(X’) \cdot (\frac{X}{X’})=\varphi(X’)\cdot e$；
  2. 当 $e \nmid X’$ 时，由上述计算公式可知，$\varphi(X) = \varphi(X’) \cdot (\frac{X}{X’}) \cdot (1-\frac{1}{e}) = \varphi(X’)\cdot (e-1)$

所以：
$$
\varphi(X) = \left\lbrace \begin{aligned}
&\varphi(X’) \cdot e, &e \mid X’ \
&\varphi(X’) \cdot (e-1), &e \nmid X’
\end{aligned} \right.
$$
不难发现，该筛法与素数线性筛同阶，因此也是线性的。

程序实现

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef long long LL;
int phi[N], prime[N], tot;
void GetPhi() {
    memset(phi, 0, sizeof phi);
    phi[1] = 1;
    tot = 0;
    for(int i=2; i < N; ++i) {
        if( !phi[i] ) {
            phi[i] = i-1;
            prime[tot++] = i;
        }
        for(int j=0; j < tot; ++j) {
            LL ret = (LL) prime[j]*i;
            if( ret >= N ) break;
            if( i%prime[j] == 0 ) {
                phi[ret] = phi[i]*prime[j]; // 对应 e 整除 X' 的情况
                break;
            }
            phi[ret] = phi[i]*(prime[j]-1); // 对应 e 不整除 X' 的情况
        }
    }
}

练习

problems categories solution
UVa/GCD Extreme(II) 欧拉函数 Code