统计小于n的质数个数。最朴素的做法是对每个数试除到√x整体O(n√n)。n 10⁶时要跑约10⁹次除法慢得不能忍。换个思路与其一个个判断“谁是质数”不如把“谁不是质数”批量划掉。2是质数 → 划掉4, 6, 8, 10, …3是质数 → 划掉9, 15, 21, …6已被划过可跳过4已划掉 → 跳过5是质数 → 划掉25, 35, …这就是埃拉托斯特尼筛法公元前3世纪就被发明出来了。但埃氏筛有个瑕疵合数会被重复划掉30被2、3、5各划一次。能不能让每个合数只被划一次能——这就是欧拉筛线性筛复杂度从O(nloglogn) 降到O(n)。今天的主线就是这三次提速。而在结尾我会给你一组实测数据证明理论最优的欧拉筛在Python里反而最慢——这是本周第二次遇到“理论更优、实测更慢”。 题目速览30秒读懂题目1计数质数LC.204返回所有小于n的质数数量。示例n 10→42,3,5,7n 0→0约束n ≤ 5×10⁶。延伸丑数LC.263 / LC.264LC.263判断n是否为丑数质因子只含2、3、5。LC.264返回第n个丑数。n 10→12丑数严格说不是筛法而是筛法的对偶形态——筛法是“排除合数”丑数是“正向生成”。 核心思路三次提速第一级试除法O(n√n)对每个x试除i从2到√x若x有大于√x的因子必有对应的小于√x的因子。n 10⁶时约10⁹次运算——不可用但它是理解后两种方法的基线。第二级埃氏筛O(nloglogn)核心找到质数就划掉它的所有倍数。两个关键优化从i*i开始划而不是2*i——更小的倍数已被之前的质数划掉外层只需到√n——任何合数≤ n必有因子≤ √n复杂度O(nloglogn)来自Σ n/p对所有质数p求和由素数定理的推论Σ 1/p ≈ loglogn得到。它非常接近线性。埃氏筛的瑕疵合数会被重复划掉。30 2×15 3×10 5×6被划3次。这就是它没能做到O(n) 的原因。第三级欧拉筛线性筛O(n)核心思想让每个合数只被它的最小质因子划掉一次。forpinprimes:ifi*pn:breakis_comp[i*p]Trueifi%p0:break# 关键的一行为什么这个break是对的设p是第一个整除i的质数则p就是i的最小质因子。此时若继续用更大的质数p去划i×p由于i的最小质因子是p且p p所以i×p的最小质因子仍然是p而不是p——这个合数本该由p来划现在被p划了一次将来还会被p再划一次重复了。所以必须停。自检恒等式合数被标记的次数 合数的个数。n 10⁶上两边都是921,500完全相等。丑数筛法的对偶形态LC.263 判断丑数反复除以2、3、5看最后是否得到1。LC.264 求第n个丑数用三指针正向生成ugly[0] 1 i2, i3, i5分别指向下一个要乘2/3/5的丑数下标 每轮取min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)作为新丑数⚠️去重必须用三个并列的if不能用elif。因为6 2×3 3×2若用elif只会推进其中一个指针6就会被加入两次。️ 图解算法手把手走一遍n 20时埃氏筛的逐轮过程轮次当前质数 i划掉的序列从i²开始本轮新划掉124, 6, 8, 10, 12, 14, 16, 188 个239, 152 个6/12/18已划35—0 个25 20结果——质数2,3,5,7,11,13,17,19共8个注意第2轮只划了9和15——12和18在第1轮就被2划掉了。这就是“从i*i开始”省下的工作量。n 20 时欧拉筛的划掉次数对照iprimes列表本轮划掉是否在i % p 0处 break2[2]4在p2处3[2,3]6, 9在p3处4[2,3]8在p2处不划125[2,3,5]10, 15在p5处6[2,3,5]12在p2处不划18、307[2,3,5,7]14在p7处关键看i4划掉8之后遇到p2因为4 % 2 0立即break不划4×3 12。为什么12的最小质因子是2它应该在i6, p2时被划掉表中确实如此。验证恒等式n 20合数有4,6,8,9,10,12,14,15,16,18共10个欧拉筛的划掉次数也是10次——完全相等无重复✓LC.264 三指针生成丑数前10个轮次×2候选×3候选×5候选取最小推进的指针12352i224353i334654i246655i5566106i2和i3并列if10———12—第 5 轮是关键×2和×3都给出6必须两个指针都推进。 代码实现Python JavaPython版classSolution:# ---------- LC.204 埃氏筛推荐简洁且实测快----------defcountPrimes(self,n:int)-int:ifn2:return0is_prime[True]*n is_prime[0]is_prime[1]Falseforiinrange(2,int(n**0.5)1):ifis_prime[i]:# 从i*i开始划更小的倍数已被之前的质数划掉forjinrange(i*i,n,i):is_prime[j]Falsereturnsum(is_prime)# ---------- LC.204 欧拉筛线性理论最优----------defcountPrimesEuler(self,n:int)-int:ifn2:return0is_comp[False]*n primes[]foriinrange(2,n):ifnotis_comp[i]:primes.append(i)forpinprimes:ifi*pn:breakis_comp[i*p]Trueifi%p0:# p 已是i的最小质因子breakreturnlen(primes)# ---------- LC.263 丑数 ----------defisUgly(self,n:int)-bool:ifn0:returnFalseforpin(2,3,5):whilen%p0:n//preturnn1# 1是丑数# ---------- LC.264 丑数II ----------defnthUglyNumber(self,n:int)-int:ugly[1]i2i3i50for_inrange(n-1):a,b,cugly[i2]*2,ugly[i3]*3,ugly[i5]*5nxtmin(a,b,c)ugly.append(nxt)# 必须用三个并列if6 2*3 3*2ifnxta:i21ifnxtb:i31ifnxtc:i51returnugly[-1]Java版classSolution{publicintcountPrimes(intn){if(n2)return0;boolean[]isPrimenewboolean[n];java.util.Arrays.fill(isPrime,true);isPrime[0]isPrime[1]false;for(inti2;(long)i*in;i){// i*i可能溢出if(isPrime[i]){for(longj(long)i*i;jn;ji){isPrime[(int)j]false;}}}intcnt0;for(booleanb:isPrime)if(b)cnt;returncnt;}publicbooleanisUgly(intn){if(n0)returnfalse;for(intp:newint[]{2,3,5}){while(n%p0)n/p;}returnn1;}publicintnthUglyNumber(intn){int[]uglynewint[n];ugly[0]1;inti20,i30,i50;for(intk1;kn;k){intaugly[i2]*2,bugly[i3]*3,cugly[i5]*5;intnxtMath.min(a,Math.min(b,c));ugly[k]nxt;if(nxta)i2;if(nxtb)i3;if(nxtc)i5;}returnugly[n-1];}}⚠️防坑提醒必看埃氏筛从i*i开始不是2*iJava里i*i可能超int比较时用(long) i * i。欧拉筛的break必须在标记之后先标is_comp[i*p] True再判断i % p 0。写反会导致i*p没被标记。LC.264去重必须用并列if用elif时6会被加入两次。⏱️ 复杂度分析面试必问方法时间复杂度空间关键试除法O(n√n)O(1)只试除到 √x埃氏筛O(nloglogn)O(n)从i*i开始划欧拉筛O(n)O(n)每个合数只被最小质因子划一次实测理论最优的欧拉筛真的最快吗CPython四种实现结果全部一致n 10⁵质数9,592个实现耗时相对埃氏筛切片赋值版0.001s1×埃氏筛朴素循环版0.004s4×欧拉筛0.012s13.4×试除法0.181s181×n 10⁶质数78,498个实现耗时相对埃氏筛切片赋值版0.019s1×埃氏筛朴素循环版0.091s4.8×欧拉筛0.143s7.6×试除法5.994s315×结论很反直觉理论上O(n)的欧拉筛实测比O(nloglogn) 的埃氏筛慢7.6倍。原因是实现层面的不是算法层面的埃氏筛的内层可以用切片赋值is_prime[i*i:n:i] [False] * k这是C层的批量写入几乎不经过Python解释器循环欧拉筛的内层必须逐个判断i % p 0并可能break这是一个纯Python层的循环每次迭代都有完整的解释开销换句话说埃氏筛用更少的“Python指令”完成了更多的工作。那还要学欧拉筛吗要三个理由换语言会反转。Java的boolean[]是连续内存、写入极快而欧拉筛的分支判断在JIT下被摊薄——在C/C/Java里两者差距会显著缩小欧拉筛常能扳回来。欧拉筛顺带得到质数列表且每个合数的最小质因子关系可用。质因数分解、欧拉函数φ、莫比乌斯函数等进阶算法都依赖线性筛的结构。它证明了一件更重要的事break那一行背后是“最小质因子唯一”这个数论事实理解它比记住代码有价值。本周第二次“理论更优、实测更慢”第一次是Brian Kernighan。两次遇到同一件事就该提炼成规则了。 举一反三6 道高频变体题题号题目与本题的关系LC.263丑数质因子判定的简化版LC.264丑数II三指针/堆筛法的对偶形态LC.1175质数排列筛 阶乘 快速幂LC.952按公因数计算最大组件大小筛 并查集LC.279完全平方数也可以用筛预处理平方数LC.204计数质数本题 面试追问模拟提前准备惊艳全场Q1欧拉筛的那行break为什么正确当p整除i时p就是i的最小质因子。此时对任何p p合数i×p的最小质因子仍是p。若现在用p去划将来还会被p再划一次——重复了。所以必须在第一个整除的p处停止。Q2怎么验证“每个合数只被划一次”用恒等式合数被标记的次数 合数的个数。n 10⁶时被标记921,500次合数也恰好921,500 个10⁶ - 78,498 - 2 921,500✓。这个恒等式可以直接写进测试脚本当断言。Q3埃氏筛为什么从i*i开始2*i, 3*i, ..., (i-1)*i这些数都含有一个小于i的质因子在之前的轮次里已经被划掉了。从i*i开始可以避免重复劳动。Q4丑数II的三指针为什么不能用elif因为6 2×3 3×2它可以由两个不同的指针产生。用elif只会推进其中一个下一轮另一个指针又给出6导致6被加入两次。三个并列的if才能保证每个候选值只推进一次。 实战小技巧刷题党必备口诀埃氏筛从i²划欧拉筛遇整除即停丑数三指针并列if防重复。模板埃氏筛 [True]*nrange(i*i, n, i)欧拉筛 primesif i % p 0: break。防坑i*i溢出用longLC.264用并列if欧拉筛先标记再break。 实际应用场景不止是刷题密码学RSA需要生成大质数筛法是基础工具哈希与随机数质数大小的哈希表容量能减少冲突数论预处理欧拉函数 φ、莫比乌斯函数μ都基于线性筛批量判定需要反复判断“某个数是否为质数”时一次筛出表比逐个试除划算得多 今日思考题实测显示Python里埃氏筛切片版比欧拉筛快7.6倍。如果面试官问“既然欧拉筛是O(n)为什么你不用它”你会怎么回答另外你能想到让欧拉筛在Python里也跑得快一些的办法吗