什么是线性筛线性筛是一种在O(N)O(N)O(N)时间复杂度内筛出111到NNN中所有质数的算法。它同时也是预处理最小质因子、欧拉函数、约数个数等数论函数的强有力框架。相比朴素的埃氏筛埃拉托斯特尼筛法O(Nlog⁡log⁡N)O(N \log \log N)O(NloglogN)的复杂度线性筛将复杂度压到了真正的线性代价是代码稍复杂一些但换来的能力远超单纯的质数筛。埃氏筛的问题埃氏筛的思想很简单从小到大遍历遇到一个质数就把它的所有倍数标记为合数。for(inti2;in;i){if(!is_comp[i]){primes.push_back(i);for(intji*2;jn;ji)is_comp[j]true;}}问题在于一个合数可能被多个质数重复标记。例如121212会被质数222标记一次又会被质数333再标记一次。这种重复操作使得复杂度无法达到线性。线性筛的核心思想线性筛的目标是每个合数只被它的最小质因子筛掉一次。设合数xxx的最小质因子为ppp则xi×px i \times pxi×p。我们希望在枚举iii时用质数ppp恰好筛掉xxx此后不再用其他质数去碰它。这就需要一个关键判断当ppp能整除iii时立即停止用更大的质数去筛i×p′i \times pi×p′因为这些合数的最小质因子已经不是p′pp′而是ppp了。代码实现与逐行解释constintMAXN1e65;intprimes[MAXN],cnt;// 收集质数boolis_comp[MAXN];// 是否为合数intminp[MAXN];// 最小质因子voidlinear_sieve(intn){for(inti2;in;i){// 如果 i 还没有被标记为合数它就是质数if(!is_comp[i]){primes[cnt]i;minp[i]i;// 质数的最小质因子是它自己}// 用已有的质数去筛合数for(intj0;jcnti*primes[j]n;j){intpprimes[j];is_comp[i*p]true;// i * p 一定是合数minp[i*p]p;// p 是 i*p 的最小质因子if(i%p0)break;// 关键一旦 p | i立刻停止}}}if (i % p 0) break;为什么关键我们手动模拟n6n6n6的过程聚焦这行代码i 2质数primes[2]。内循环p2筛掉444。i % 2 0break。i 3质数primes[2,3]。内循环p2筛掉6663%2 ! 0继续p3筛掉999break。i 4合数minp[4]2。内循环p2筛掉8884%20break。注意4 不会和 p3 相乘因此121212不会在这里被筛。i 5质数筛掉10,1510,1510,15。i 6合数minp[6]2。内循环p2筛掉1212126%20break。可以看到121212被i6, p2筛掉而不是被i4, p3筛掉。这正是因为我们每次都在i % p 0时 break保证了筛掉每个合数所用的质数恰好是该合数的最小质因子。推广到一般情况对于当前iii设其最小质因子为p0p_0p0​。当我们枚举质数ppp去乘iii时若pp0p p_0pp0​则ppp是i×pi \times pi×p的最小质因子合理筛掉。若pp0p p_0pp0​即i % p 0ppp恰好是i×pi \times pi×p的最小质因子筛掉后应立即停止。因为下一个更大的质数p′pp′乘iii所得的i×p′i \times pi×p′它的最小质因子是p0p_0p0​而不是p′pp′应该留给后续更大的i′ii′用p0p_0p0​去筛。这样每个合数都只会进入内循环一次复杂度严格O(N)O(N)O(N)。线性筛的扩展能力线性筛的威力远不止找出质数。在筛的过程中我们可以顺便求出最小质因子、欧拉函数、约数个数等信息因为它们都满足积性函数的递推性质。1. 最小质因子上文的minp数组已经给出。minp[i]记录了iii的最小质因子。这使得后续单个数质因数分解的复杂度降为O(log⁡N)O(\log N)O(logN)voidfactorize(intx){while(x1){intpminp[x];intcnt0;while(x%p0)x/p,cnt;// 输出或存储 (p, cnt)}}2. 欧拉函数φ(n)\varphi(n)φ(n)欧拉函数φ(n)\varphi(n)φ(n)表示111到nnn中与nnn互质的数的个数。它满足φ(p)p−1\varphi(p) p - 1φ(p)p−1ppp是质数若p∣ip \mid ip∣i则φ(i×p)φ(i)×p\varphi(i \times p) \varphi(i) \times pφ(i×p)φ(i)×p若p∤ip \nmid ip∤i则φ(i×p)φ(i)×(p−1)\varphi(i \times p) \varphi(i) \times (p - 1)φ(i×p)φ(i)×(p−1)我们可以把它整合到线性筛中intphi[MAXN];voidsieve_with_phi(intn){phi[1]1;for(inti2;in;i){if(!is_comp[i]){primes[cnt]i;phi[i]i-1;}for(intj0;jcnti*primes[j]n;j){intpprimes[j];is_comp[i*p]true;if(i%p0){phi[i*p]phi[i]*p;break;}phi[i*p]phi[i]*(p-1);}}}3. 约数个数设d(n)d(n)d(n)为nnn的约数个数a(n)a(n)a(n)为nnn的最小质因子的指数。在线性筛中同样可以维护若nnn为质数d(n)2d(n)2d(n)2a(n)1a(n)1a(n)1。若p∤ip \nmid ip∤i则d(i×p)d(i)×2d(i \times p) d(i) \times 2d(i×p)d(i)×2a(i×p)1a(i \times p) 1a(i×p)1。若p∣ip \mid ip∣i则d(i×p)d(i)/(a(i)1)×(a(i)2)d(i \times p) d(i) / (a(i)1) \times (a(i)2)d(i×p)d(i)/(a(i)1)×(a(i)2)a(i×p)a(i)1a(i \times p) a(i) 1a(i×p)a(i)1。代码类似不再赘述。线性筛 vs 埃氏筛埃氏筛线性筛时间复杂度O(Nlog⁡log⁡N)O(N \log \log N)O(NloglogN)O(N)O(N)O(N)空间复杂度O(N)O(N)O(N)O(N)O(N)O(N)是否重复标记合数是否能否同时求最小质因子需要额外处理可以直接整合能否递推欧拉函数等不方便非常方便代码复杂度简单略复杂在N≤107N \le 10^7N≤107时埃氏筛的实际速度与线性筛相差不大。但当需要维护最小质因子、欧拉函数等附加信息时线性筛是首选框架。总结线性筛通过“每个合数只被最小质因子筛掉一次”的核心机制将筛法复杂度压到O(N)O(N)O(N)并提供了一个可以嵌入多种积性函数递推的框架。理解if(i % p 0) break;这句话就理解了线性筛的全部精髓。对于算法竞赛线性筛是处理10710^7107范围内数论预处理的标准工具也是后续质因数分解、互质计数、狄利克雷卷积等问题的基础。