找质数不止暴力试除——埃拉托色尼筛法与线性筛从入门到精通写在前面质数这玩意儿从小学就开始打交道了。但直到我学算法的时候才发现找质数这件事远不是从2试到n那么简单。面试的时候被问过怎么找出1到100万之间的所有质数如果你回答每个数都试除一下面试官可能会礼貌地点点头然后在心里给你打个低分。因为对于大范围的质数筛选有一种古老而优雅的算法——埃拉托色尼筛法它的效率比暴力法高出几个数量级。这篇文章我会从最基本的暴力试除讲起逐步深入到埃氏筛、优化版埃氏筛最后讲到线性筛欧拉筛。每种算法都配上代码、复杂度分析和图解。看完这篇找质数这件事你就算彻底毕业了。一、暴力试除最朴素的想法先别急着看筛法咱们从最基础的写法开始。判断一个数 n 是不是质数最直观的想法就是从 2 到 n-1看看有没有能整除 n 的数。defis_prime(n):ifn2:returnFalseforiinrange(2,n):ifn%i0:returnFalsereturnTruedeffind_primes_bruteforce(n):return[iforiinrange(2,n1)ifis_prime(i)]这个写法的时间复杂度是 O(n^2)找 1 到 n 的所有质数需要 O(n^2) 的时间。稍微优化一下我们只需要试除到 sqrt(n) 就行了——因为如果 n 有一个大于 sqrt(n) 的因子那它必然对应一个小于 sqrt(n) 的因子。importmathdefis_prime_optimized(n):ifn2:returnFalseforiinrange(2,int(math.sqrt(n))1):ifn%i0:returnFalsereturnTrue优化后判断单个质数的时间复杂度降到了 O(sqrt(n))找 1 到 n 的所有质数是 O(n*sqrt(n))。对于小数据量够用了但如果 n 10^6这个算法就要算好几秒根本没法用。二、埃拉托色尼筛法两千年前的大智慧埃拉托色尼筛法Sieve of Eratosthenes是古希腊数学家埃拉托色尼在公元前3世纪提出的。它的核心思想非常巧妙如果我知道一个数是质数那它的所有倍数一定不是质数。2.1 算法步骤列出从 2 到 n 的所有数从 2 开始把 2 的所有倍数4, 6, 8…标记为合数找到下一个未被标记的数3把它的所有倍数标记为合数重复这个过程直到处理完 sqrt(n) 为止剩下未被标记的数就是质数我用一张图展示这个过程从图上可以看到每找到一个质数 p就把 p 的倍数全部筛掉。最终剩下的就是质数。2.2 基础代码实现defsieve_of_eratosthenes(n):# 初始化假设所有数都是质数is_prime[True]*(n1)is_prime[0]is_prime[1]False# 从 2 开始筛p2whilep*pn:ifis_prime[p]:# 从 p*p 开始标记步长为 p# 为什么从 p*p 开始因为 p*2, p*3... 已经被更小的质数筛过了foriinrange(p*p,n1,p):is_prime[i]Falsep1# 收集所有质数return[iforiinrange(2,n1)ifis_prime[i]]# 测试print(sieve_of_eratosthenes(100))# 输出: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]2.3 复杂度分析时间复杂度O(n * log(log n))这个复杂度看起来有点奇怪怎么来的简单解释一下质数定理告诉我们小于 n 的质数大约有 n / ln(n) 个。对于每个质数 p我们需要标记 n/p 个倍数。总操作次数大约是n/2 n/3 n/5 n/7 ... ≈ n * log(log n)空间复杂度O(n)布尔数组对于 n 10^6埃氏筛只需要几毫秒而暴力法要好几秒。差距就是这么大。三、埃氏筛的优化还能更快吗基础版埃氏筛已经很快了但还有几个优化点可以挖掘。3.1 优化一只筛奇数除了 2 以外所有偶数都不是质数。那我们干脆只存奇数省一半空间。defsieve_optimized(n):ifn2:return[]# 只存奇数索引 i 对应数字 2*i 1size(n1)//2is_prime[True]*size is_prime[0]False# 1 不是质数# 从 3 开始步长为 2只处理奇数forpinrange(3,int(n**0.5)1,2):ifis_prime[p//2]:# 从 p*p 开始步长为 2*p只标记奇数倍数foriinrange(p*p,n1,2*p):is_prime[i//2]Falsereturn[2][2*i1foriinrange(1,size)ifis_prime[i]]这个优化把空间 roughly 减半实际运行速度也有明显提升。3.2 优化二分段筛如果 n 非常大比如 10^12内存放不下整个数组怎么办用分段筛。思路是先筛出 sqrt(n) 以内的所有质数然后用这些质数去筛各个区间段。defsegmented_sieve(low,high):# 分段筛找出 [low, high] 区间内的所有质数limitint(high**0.5)1base_primessieve_of_eratosthenes(limit)# 标记当前区间的合数is_prime[True]*(high-low1)forpinbase_primes:# 找到第一个大于等于 low 的 p 的倍数startmax(p*p,(lowp-1)//p*p)forjinrange(start,high1,p):is_prime[j-low]False# 处理 low 1 的情况iflow1:is_prime[0]Falsereturn[lowiforiinrange(len(is_prime))ifis_prime[i]]分段筛的空间复杂度是 O(sqrt(n) segment_size)可以处理超大范围的质数查询。四、线性筛欧拉筛每个合数只筛一次埃氏筛虽然高效但有一个小缺陷某些合数会被重复筛多次。比如 30 215 310 5*6它会被 2、3、5 各筛一次。线性筛也叫欧拉筛解决了这个问题保证每个合数只被它的最小质因子筛一次。这样总操作次数严格是 O(n)不会再有冗余。4.1 核心思想线性筛维护一个质数列表。对于每个数 i用它去乘以已有的每个质数 p如果 i % p 0说明 p 是 i 的最小质因子此时 break否则i * p 的最小质因子就是 p标记 i*p 为合数这样做的关键是每个合数只被它的最小质因子筛一次。4.2 代码实现deflinear_sieve(n):# 线性筛欧拉筛# 时间复杂度: O(n)# 每个合数只被最小质因子筛一次is_prime[True]*(n1)is_prime[0]is_prime[1]Falseprimes[]foriinrange(2,n1):ifis_prime[i]:primes.append(i)# 用 i 乘以每个已知的质数forpinprimes:ifi*pn:breakis_prime[i*p]False# 关键如果 p 是 i 的最小质因子停止ifi%p0:breakreturnprimes# 测试print(linear_sieve(100))4.3 为什么线性筛是 O(n)关键在于那个 break。当 i % p 0 时p 是 i 的最小质因子。对于更大的质数 p2i * p2 的最小质因子仍然是 p因为 p 整除 i所以 i * p2 应该由 p 来筛而不是 p2。这样每个合数只被筛一次总操作次数就是 n 次严格 O(n)。五、三种算法综合对比算法时间复杂度空间复杂度核心思想适用场景暴力试除O(n*sqrt(n))O(1)逐个判断单个质数判断埃氏筛O(n*log(log n))O(n)质数的倍数标记合数范围质数筛选线性筛O(n)O(n)每个合数只被最小质因子筛大范围/高频查询实际测试中n 10^7暴力法几十秒到几分钟埃氏筛约 1 秒线性筛约 0.5 秒对于一般的面试题写埃氏筛就够了。如果题目对性能要求极高或者需要预处理大量质数用线性筛。六、质数在实际中的应用质数不是纯数学玩具它在计算机科学中有着广泛的应用6.1 RSA加密RSA 是目前最常用的非对称加密算法之一。它的安全性基于一个数学事实把两个大质数相乘很容易但把乘积分解回两个质数极其困难。RSA 的密钥生成过程随机选两个大质数 p 和 q通常几百位计算 n p * q公钥是 (n, e)私钥是 (n, d)加密c m^e mod n解密m c^d mod n没有私钥的人要从 n 分解出 p 和 q对于大数来说计算量是不可承受的。6.2 哈希表容量设计哈希表时把容量设为质数可以减少冲突。因为质数和大多数数互质散列分布更均匀。6.3 伪随机数生成线性同余生成器LCG中模数 m 通常选大质数这样生成的伪随机数周期更长、分布更均匀。6.4 循环群与密码学在模 pp 为质数的乘法群中每个非零元素都有乘法逆元。这个性质在椭圆曲线密码学、Diffie-Hellman 密钥交换等算法中都有重要应用。七、素数定理质数有多稀疏你可能好奇质数在整数中到底占多大比例素数定理告诉我们小于 n 的质数个数大约是 n / ln(n)。也就是说质数的密度随着 n 增大而逐渐降低但永远不会消失。n实际质数个数n/ln(n) 近似误差100252212%1,00016814514%10,0001,2291,08612%100,0009,5928,6869%1,000,00078,49872,3828%可以看到n/ln(n) 的近似效果随着 n 增大越来越好。这个定理也解释了为什么筛法比暴力法快那么多——因为质数越来越稀疏需要标记的倍数也越来越少。八、面试中的质数问题面试中质数相关的题目通常有几种类型8.1 判断单个数是否为质数写试除到 sqrt(n) 的版本就够了。注意处理 n 2 的情况。8.2 找出范围内的所有质数写埃氏筛。如果面试官追问优化提一下只筛奇数或者线性筛。8.3 质因数分解defprime_factorization(n):factors{}d2whiled*dn:whilen%d0:factors[d]factors.get(d,0)1n//d d1ifn1:factors[n]factors.get(n,0)1returnfactors# 测试: 360 2^3 * 3^2 * 5print(prime_factorization(360))# {2: 3, 3: 2, 5: 1}8.4 第 k 个质数用筛法预处理然后直接查表。或者用二分 素数计数函数。九、总结找质数这件事从暴力到筛法体现了算法优化的核心思想利用已知信息避免重复计算。暴力试除逐个判断O(n*sqrt(n))适合单个质数判断埃氏筛质数的倍数标记合数O(n*log(log n))适合范围筛选线性筛每个合数只筛一次O(n)适合大范围/高频查询面试建议先写埃氏筛这是标准答案主动提优化从 p*p 开始、只筛奇数如果时间充裕展示线性筛体现深度了解质数的实际应用RSA、哈希表展示知识面最后送一句话质数就像编程里的基础工具看似简单但用好了能解决大问题。如果这篇文章对你有帮助欢迎点赞收藏有任何问题可以在评论区留言我会尽量回复。后续会持续更新算法相关的干货内容欢迎关注本文原创转载请注明出处。