线性筛
埃氏筛能够做到在 \(O(n\log \log n)\) 的时间复杂度内筛出 \([1, n]\) 内的质数。然而某些时候我们要求筛法的时间复杂度降低到 \(O(n)\)，或者想求出每个数的最小质因子，以及筛某些特殊的函数。这时候需要用到线性筛。
欧拉筛
欧拉筛能保证每个数只被其最小的质因子筛一遍。
这段代码可以保证 pri[j] 一定是 i * pri[j] 的最小质因子。
欧拉筛中，第 \(6\) 行的 break 是保证时间复杂度的核心。这句代码的意思是，如果 \(i\) 中包含质因子 pri[j]，那么所有排在其后面的 pri[j] 都不可能成为对应的 i * pri[j] 的最小质因子，因为 \(i\) 中包含的 pri[j0] 一定是更小的质因子。
综上，每个合数只会被筛一次，时间复杂度为 \(O(n)\)。
欧拉筛求欧拉函数
欧拉函数 \(\varphi(n)\) 定义为小于等于 \(n\) 且与 \(n\) 互质的正整数的个数。特别的，\(\varphi(1)=1\)。
\[
\varphi(n)=\sum_{i=1}^{n}{[gcd(i,n)=1]}
\]
通过容斥原理可以得到 \(\varphi(n)\) 的一种计算式：
\[
\begin{align*}
\varphi(n)=\ &n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_k})\\
=\ &n\prod_{i=1}^{k}{(1-\frac{1}{p_i})}
\end{align*}
\]
其中 \(k\) 为 \(n\) 的质因子的数量，\(p_i\) 为第 \(i\) 个质因子。形式化的：
\[
n={p_1}^{a_1}{p_2}^{a_2}{p_3}^{a_3}\cdots {p_k}^{a_k}
\]
因此，我们可以通过在欧拉筛中求出每个数的最小质因子 \(p_1\)，通过它来快速求出每个数的欧拉函数：
\[
\varphi(n)=
\begin{cases}
p_1\times\varphi(\frac{n}{p_1}),&p_1\mid\frac{n}{p_1}\\
(p_1-1)\times\varphi(\frac{n}{p_1}),&p\nmid\frac{n}{p_1}
\end{cases}
\]
此公式可通过定义直接导出。由欧拉筛求区间 \([1,n]\) 范围内所有数字的欧拉函数，时间复杂度 \(O(n)\)。
明灯筛
在洛谷上看到的新科技。欧拉筛筛复杂的积性函数时，需要额外记录最小质因子的次数，非常复杂。我们可以直接让每个数字都被最小质因子的次幂筛掉。