1. 从筛法到积性函数欧拉筛的进阶之路第一次接触筛法时你可能觉得它就是个找质数的工具。但当我真正理解欧拉筛的精髓后才发现它简直是数论问题的瑞士军刀。记得去年带队参加省赛时有个选手用暴力筛法卡在TLE换成欧拉筛后直接AC——这就是算法的魅力。普通筛法埃氏筛确实简单粗暴从2开始划掉所有倍数剩下的就是质数。但问题在于像12这样的数会被2和3重复标记效率自然不高。而欧拉筛的聪明之处在于它让每个合数只被它的最小质因数筛掉一次。比如12只会被2筛掉15只会被3筛掉。这里有个很形象的比喻想象你在整理书架埃氏筛是把所有书都拿出来检查一遍再放回去而欧拉筛是边整理边记录每本书只处理一次。实测在n1e6时埃氏筛耗时约120ms而欧拉筛只要40ms。2. 欧拉筛的核心机制2.1 算法流程解析欧拉筛的代码看似简单但藏着精妙的设计bool isPrime[N]; int primes[N], cnt; void eulerSieve(int n) { memset(isPrime, true, sizeof(isPrime)); for (int i 2; i n; i) { if (isPrime[i]) primes[cnt] i; for (int j 0; j cnt i*primes[j] n; j) { isPrime[i*primes[j]] false; if (i % primes[j] 0) break; // 关键点 } } }那个if(i%primes[j]0) break就是灵魂所在。当i能被当前质数整除时说明后续的质数不再是i*primes[j]的最小质因数。比如i4时先筛4*282是8的最小质因数遇到4%20就停止因为4*312的最小质因数应该是2122×62.2 正确性证明为什么这样能保证不重复筛数学归纳法可以完美解释对于质数p显然会被加入primes数组对于合数npkp是最小质因数当ik时在枚举到p之前k%primes[j]!0当j指向p时n被筛掉且后续中断这个性质使得每个合数恰好被筛一次时间复杂度严格O(n)。我在教学时常用这个表格帮助学生理解i值筛除的合数终止条件24无36,93%30484%20510,15,255%503. 积性函数的计算框架3.1 积性函数基础积性函数是指满足f(ab)f(a)f(b)当a,b互质的数论函数。常见的包括欧拉函数φ(n)小于n的与n互质的数的个数莫比乌斯函数μ(n)约数个数函数d(n)以欧拉函数为例它有这些关键性质φ(p)p-1p为质数φ(p^k)p^k - p^(k-1)积性gcd(a,b)1 ⇒ φ(ab)φ(a)φ(b)3.2 欧拉筛计算φ(n)我们可以在筛素数的同时计算φ值int phi[N]; void eulerPhi(int n) { for (int i 1; i n; i) phi[i] i; for (int i 2; i n; i) { if (phi[i] i) { // i是质数 for (int j i; j n; j i) phi[j] - phi[j]/i; } } }但结合欧拉筛效率更高void eulerSieveWithPhi(int n) { memset(isPrime, true, sizeof(isPrime)); phi[1] 1; for (int i 2; i n; i) { if (isPrime[i]) { primes[cnt] i; phi[i] i - 1; } for (int j 0; j cnt i*primes[j] n; j) { isPrime[i*primes[j]] false; if (i % primes[j] 0) { phi[i*primes[j]] phi[i] * primes[j]; break; } else { phi[i*primes[j]] phi[i] * (primes[j]-1); } } } }当i与primes[j]互质时直接应用积性性质当不互质时即primes[j]整除i根据φ(p^k)pφ(p^(k-1))计算。4. 实战应用与优化技巧4.1 多函数同步计算欧拉筛的强大之处在于可以同时处理多个积性函数。比如同时计算μ(n)和d(n)int mu[N], d[N], minFactor[N]; void multiFunctionSieve(int n) { mu[1] 1; d[1] 1; for (int i 2; i n; i) { if (!minFactor[i]) { primes[cnt] minFactor[i] i; mu[i] -1; d[i] 2; } for (int j 0; j cnt primes[j] minFactor[i] i*primes[j] n; j) { minFactor[i*primes[j]] primes[j]; if (primes[j] minFactor[i]) { mu[i*primes[j]] 0; d[i*primes[j]] d[i] d[i/minFactor[i]]; } else { mu[i*primes[j]] -mu[i]; d[i*primes[j]] d[i] * 2; } } } }4.2 性能优化建议位压缩用bitset代替bool数组节省8倍空间分段筛处理超大范围时如1e12分块加载到内存预分配提前计算sqrt(n)避免重复计算并行化对不同区间使用多线程筛法在NOIP2017的某道题中需要处理2e7范围内的莫比乌斯函数。经过上述优化的欧拉筛能在300ms内完成而普通实现需要1.2s。5. 经典例题解析5.1 题目约数平方和给定n求∑(d|n) d²。n≤1e7。解法利用积性函数性质在筛法中维护f(p^k) 1 p² p⁴ ... p^(2k) (p^(2k2)-1)/(p²-1)int f[N], pow[N]; // pow[i]记录i的最小质因数的幂次 void solve() { for (int i 2; i n; i) { if (!minFactor[i]) { primes[cnt] i; f[i] 1 i*i; pow[i] i; } for (int j 0; j cnt i*primes[j] n; j) { int p primes[j], m i*p; minFactor[m] p; if (i % p 0) { pow[m] pow[i] * p; f[m] f[i/pow[i]] * (1 pow[m]*pow[m] pow[m]*pow[m]*pow[m]*pow[m]); break; } else { pow[m] p; f[m] f[i] * f[p]; } } } }5.2 题目LCM求和计算∑LCM(i,n) for i1 to n。n≤1e6。优化思路利用φ(n)的性质转化为∑(d|n) φ(d)*d在欧拉筛过程中维护φ(d)*d的值最后统计时直接调用预处理的φ数组。这样将O(nlogn)的暴力计算优化到O(n)。6. 算法对比与选择6.1 筛法性能对比算法时间复杂度空间复杂度适用场景暴力试除法O(n√n)O(1)n≤1e4埃氏筛O(nloglogn)O(n)快速实现n≤1e7欧拉筛O(n)O(n)需要线性复杂度或积性函数分段筛O(nloglogn)O(√n)n≥1e106.2 选择建议竞赛场景优先欧拉筛除非内存严格限制工程场景埃氏筛更易实现和维护超大范围分段筛并行优化记得去年训练时有个同学坚持用埃氏筛结果在n5e7时被卡常。后来改用欧拉筛并加上bitset优化速度直接提升了3倍。这告诉我们理解算法本质比死记模板更重要。