线性筛

埃氏筛能够做到在 \(O(n\log \log n)\) 的时间复杂度内筛出 \([1, n]\) 内的质数。然而某些时候我们要求筛法的时间复杂度降低到 \(O(n)\)，或者想求出每个数的最小质因子。这时候需要用到线性筛（欧拉筛）。

线性筛

线性筛能保证每个数只被其最小的质因子筛一遍。

int prime[N], nPrime[N], cnt;

for(int i = 2; i <= n; i++) {
    if(!nPrime[i]) prime[++cnt] = i;
    for(int j = 1; j <= cnt; j++) {
        if(i * prime[j] > n) break;
        noPrime[i * prime[j]] = 1;
        if(i % prime[j] == 0) break;
    }
}

这段代码可以保证 prime[j] 一定是 i * prime[j] 的最小质因子。

线性筛中，第 \(6\) 行的 break 是保证时间复杂度的核心。这句代码的意思是，如果 \(i\) 中包含质因子 prime[j]，那么所有排在其后面的 prime[j] 都不可能成为对应的 i * prime[j] 的最小质因子，因为 \(i\) 中包含的 prime[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)\)。