欧拉筛线性筛算法详解3 个关键步骤与 2 个核心证明在算法竞赛和编程面试中素数筛选是一个经典问题。欧拉筛又称线性筛以其**O(n)**的时间复杂度成为最优解方案。本文将彻底拆解这一算法的设计思想通过三个关键步骤和两个数学证明让你不仅掌握代码实现更能理解其背后的数学原理。1. 算法背景与核心思想传统筛法如埃氏筛存在一个明显缺陷某些合数会被多次标记。例如数字12在筛选2的倍数时被标记一次在筛选3的倍数时又被重复标记。这种重复操作导致埃氏筛的时间复杂度为O(n log log n)。欧拉筛的突破性在于它确保每个合数只被其最小质因数筛除一次。这一特性通过以下设计实现双重循环结构外层循环遍历每个数i内层循环遍历已知质数prime[j]提前终止机制当i能被prime[j]整除时立即终止内层循环动态维护质数表实时更新当前发现的质数集合def euler_sieve(n): is_prime [True] * (n1) primes [] for i in range(2, n1): if is_prime[i]: primes.append(i) for p in primes: if i*p n: break is_prime[i*p] False if i % p 0: break return primes2. 三个关键操作步骤解析2.1 质数收集阶段当遍历到数字i时若is_prime[i]仍为True说明i未被任何小于它的数筛除因此i必为质数。此时将i加入质数列表primes中。注意这个判断必须放在内层循环之前确保新发现的质数能立即参与后续筛选2.2 合数标记阶段对于当前数字i和每个已知质数p标记i*p为合数。这里存在两个关键优化范围控制当i*p超过n时立即终止循环标记顺序总是用较小的质数先进行标记2.3 提前终止条件当发现i能被p整除时即i % p 0立即终止内层循环。这是保证线性时间复杂度的关键其数学原理将在第4节详细证明。3. 算法正确性的两个核心证明3.1 命题一每个合数都会被筛除对于任意合数x设其最小质因数为p则存在k x/p。由于p是最小质因数必有k ≥ p。算法在遍历到i k时质数p已在primes列表中因p ≤ k内层循环处理p时会标记i*p x为合数在ik的循环中x必定被标记反例验证假设不采用最小质因数筛选如数字453×15。若允许用5筛选当i9时标记45但此时9%30会提前终止导致45被3在i15时标记。3.2 命题二每个合数只被筛一次关键在于理解为何当i % p 0时需要终止。设i k*p则对于下一个质数q p本应标记iq kp*q但这个数会在i k*q时被p标记因为p q因此当前循环无需继续数学表达i × q (k × p) × q (k × q) × p i × p (其中i k × q i)4. 复杂度分析与实际应用4.1 时间复杂度证明每个合数仅被标记一次每个i都经历常数次操作因此总操作次数为质数判断O(n)合数标记O(n)因为n以内合数约n/ln n个每个标记一次总复杂度为严格的O(n)优于埃氏筛的O(n log log n)。4.2 空间复杂度需要两个主要数据结构大小为n的布尔数组is_prime → O(n)质数列表primes存储π(n)≈n/ln n个质数 → O(n/ln n)总空间复杂度仍为O(n)。4.3 性能对比测试下表展示不同算法在n1e6时的实际表现算法类型执行时间(ms)内存消耗(MB)暴力判断法12501.2埃氏筛453.8欧拉筛284.1虽然欧拉筛内存占用略高但在大规模数据时时间优势明显。当n1e7时欧拉筛仍能在300ms内完成而埃氏筛需要约500ms。5. 算法变形与扩展应用欧拉筛不仅能筛选素数还可扩展用于计算数论函数5.1 最小质因数记录修改算法记录每个数的最小质因数min_prime [0]*(n1) for i in range(2, n1): if min_prime[i] 0: primes.append(i) min_prime[i] i for p in primes: if i*p n: break min_prime[i*p] p if i % p 0: break5.2 欧拉函数计算利用线性筛可在O(n)时间内计算1~n的欧拉函数值phi [0]*(n1) phi[1] 1 for i in range(2, n1): if not phi[i]: primes.append(i) phi[i] i-1 for p in primes: if i*p n: break if i % p 0: phi[i*p] phi[i]*p break else: phi[i*p] phi[i]*(p-1)掌握欧拉筛的核心在于理解其最小质因数筛选原则。这种思想不仅适用于素数筛选还可推广到其他数论问题的优化解决方案中。