筛法、筛法求欧拉函数、因数个数

筛法基础

给定 $n$，求出 $1$ ~ $n$ 中所有的质数，封装成 get_prime(int n) 的数组。

暴力

不就是验证质数 $n$ 遍吗？

int p[N], cnt;
bool is_prime(int x)
{
	if(x == 1) return false;
	for(int i = 2; i * i <= x; i++)
		if(x % i == 0)
			return false;
	return true;
}
void get_prime(int n)
{
	for(int i = 1; i <= n; i++)
		if(is_prime(i))
			p[++cnt] = i;
}

验证质数的时间复杂度是 $O(\sqrt{\smash[b]{n}})$，所以总体的时间复杂度是 $O(\sqrt{\smash[b]{n}}\times n)$，非常高。

埃氏筛

质数的因数只有 $1$ 和它本身，所以遍历到非 $1$ 的一个数就把所有它的倍数（除了它自己）标记，遍历到后没有被标记的就是质数。

bool vis[N]; 
vector<int> prime;
void get_prime(int n)//埃氏筛
{
	for(int i = 2; i <= n; i++)
	{
		if(!vis[i]) prime.push_back(i);
		for(int j = i * i; j <= n; j += i)//i*i是个小优化，后面会讲
			vis[j] = true;
	}
} 

其中第 8 行 i*i是个小优化，因为比如遍历到 $j = (i - 1) \times i$，$j$ 这个数就在 $i - 1$ 时被标记过了。

这个时间复杂度判断较为复杂，我直接告诉答案了 $O(n \log \log n)$。

线性筛（欧拉筛）

为什么埃氏筛慢？因为它重复标记了一些数。

我们规定一个规则，一个数 $m$ 只能被一个 $m$ 的最小质因子 $p_j$，再乘上剩下的数 $i$ 标记。

我们把 $j$ 的循环变为遍历当前存储的质数，持续把 $p_j\times i$ 这个数标记。
如果 $p_j$ 是 $i$ 的因数，跳出循环。

因为 $p_j$ 是 $i$ 的因数，说明 $p_j$ 是 $i$ 的最小质因子（因为质数是从大到小遍历的），那么下一个就不是 $p_j \times i$ 的最小质因子了，不符合上面的规则，先跳出循环。
注意：当 $p_j$ 是 $i$ 的因数时也会标记 $p_j \times i$，下一次才不标记了。

void get_prime(int n)//线性筛，欧拉筛 
{
	for(int i = 2; i <= n; i++)
	{
		if(!vis[i]) prime.push_back(i);
		for(int j = 0; j < prime.size(); j++)
		{
			vis[p[j] * i] = true;
			if(i % p[j] == 0) break;//这两句千万别搞反了！！！
		}
	}
}

按照我们的规定，每个数只被标记了一次，所以时间复杂度为 $O(n)$，而且正因为如此，它叫线性筛。

筛法基础总结

我们找到了 3 种获取质数的方法，分别为：

1. 暴力，$O(\sqrt{\smash[b]{n}})$
2. 埃氏筛，$O(n \log \log n)$
3. 线性筛（欧拉筛），$O(n)$

我们一般都使用线性筛。

那么，筛还有什么作用呢？

筛法求欧拉函数

刚刚学了欧拉筛，这次怎么来了个欧拉函数？

求 $\varphi(1)$ ~ $\varphi(n)$。

前置芝士补充

知道的可以跳过此阶段。

基本性质

首先我们要知道一些基本性质。

1. 若 $p$ 是质数，则 $\varphi(p)=p-1$。
2. 若 $p$ 是质数，则 $\varphi(p^k)=(p-1)\times p^k-1$。
   我们把 $1$ ~ $p^k$ 分为 $p^{k-1}$ 个节，为 $1…p…2 \times p…3\times p…p^k$。
   每个节有 $p-1$ 个数与 $p$ 互质，所以$\varphi(p^k)=(p-1)\times p^k-1$。
3. 根据积性函数，若 $n$ 和 $m$ 互质，则 $\varphi(n\times m) = \varphi(n) \times \varphi(m)$。

计算

根据唯一分解定理 $n=\displaystyle\prod_{i=1}^{s}p_i^{a_i} = p_1^{a_1} \times p_2^{a_2}\times … \times p_s^{a_s}$。
$\varphi(n)=\displaystyle\prod_{i=1}^{s}\varphi(p_i^{a_i})\\ \hspace{0.81cm}=\displaystyle\prod_{i=1}^{s}p_i^{a_i-1}(p_i-1)\\ \hspace{0.81cm}=\displaystyle\prod_{i=1}^{s}p_i^{a_i}(1-\frac{1}{p_i})\\ \hspace{0.81cm}=\displaystyle\prod_{i=1}^{s}p_i^{a_i}\times\displaystyle\prod_{i=1}^{s}(1-\frac{1}{p_i})\\ \hspace{0.81cm}=n\times\displaystyle\prod_{i=1}^{s}\frac{p_i-1}{p_i}\\$

筛法实现

若 $i$ 是质数，$phi_i=i-1$。
在线性筛中，每个合数 $m$ 都是被最小的质因子筛掉的。设 $p_j$ 是 $m$ 的最小质因子，则 $m$ 通过 $m=p_j\times i$ 筛掉。
分为 $2$ 种情况：

1. 若 $i$ 能被 $p_j$ 整除，则 $i$ 包含了 $m$ 的所有质因子。
   $\varphi(m)=m\times \displaystyle\prod_{i=1}^{s}\frac{p_i-1}{p_i}\newline \hspace{0.91cm}=p_j\times i \times \displaystyle\prod_{i=1}^{s}\frac{p_i-1}{p_i}\\ \hspace{0.91cm}=p_j\times \varphi(i)$
2. 否则 $i$ 和 $p_j$ 互质。
   $\varphi(m)=\varphi(p_j\times i)\\ \hspace{0.91cm}=\varphi(p_j) \times \varphi(i)\\ \hspace{0.91cm}=(p_j -1) \times \varphi(i)$

$\texttt{Code}$

int p[N], cnt;
bool vis[N];
int phi[N];
void get_phi(int n)
{
	phi[i] = 1;
	for(int i = 2; i <= n; i++)
	{
		if(!vis[i])
			p[++cnt] = i, phi[i] = i - 1;
		for(int j = 1; j <= cnt && p[j] * i <= n; j++)
		{
			int m = i * p[j];
			vis[m] = true;
			if(i % p[j] == 0)
			{
				phi[m] = p[j] * phi[i];
				break;
			}
			else
				phi[m] = (p[j] - 1) * phi[i];
		}
	}
}

筛法求因数个数

给定 $n$，求 $1$ ~ $n$ 每个数的因数个数。

前置知识补充

这里不在强调，可以去这里看。

若 $n=\displaystyle\prod_{i=1}^{s}p_i^{a_i}$，则因数个数 $d(n)$ 可以表示为：

$$d(n)=\displaystyle\prod_{i=1}^{s}(a_i+1)$$

筛法实现

1. 初始化
   创建数组 $d$ 和 $a$，分别用于存储因数个数和每个数质因数分解的最小质因数的指数。
   初始化 $d$ 和 $a$，$d_1=1,a_1=0$。
2. 质数处理
   若 $p$ 为质数，则 $d_p=2,a_p=1$。
3. 筛
   $m=p_j\times i$。
   若 $i\mod p_j=0$，$a_m=a_i+1$，$d_m=\frac{d_i}{a_m}\times(a_m+1)$。
   否则 $a_m=1,d_m=d_i\times 2$

$\texttt{Code}$

int p[N], cnt, a[N], d[N];
bool vis[N];
void get_d(int n)
{
	d[1] = 1;
	for(int i = 2; i <= n; i++)
	{
		if(!vis[i])
			p[++cnt] = i, a[i] = 1, d[i] = 2;
		for(int j = 1; j <= cnt && p[j] * i <= n; j++)
		{
			int m = p[j] * i;
			vis[m] = i;
			if(i % p[j] == 0)
			{
				a[m] = a[i] + 1, d[m] = d[i] / a[m] * (a[m] + 1);
				break;
			}
			a[m] = 1, d[m] = d[i] * 2; 
		}
	}
}

总结和预告

这次我们学习了筛法，分为:

• 埃氏筛，$O(n\log\log n)$
• 线性筛（欧拉筛），$O(n)$

并且使用线性筛（欧拉筛）。

我们还学习了如何使用筛法计算 $1$ ~ $n$ 中的：

• 质数
• 欧拉函数（$\varphi$）
• 求因数个数

下一次，我们会学习筛法求因数和莫比乌斯函数（不知道你会鸽多久）。

还有，欢迎来到我的博客玩哦！