素数判断与筛法全解析：从暴力到埃氏筛、线性筛

判断一个数是不是素数几乎是每个编程新手接触到的第一个“有点意思”的算法题。表面上看它只需要一个循环加一个取模但真正把它写对、写快其实涉及边界条件、数学推导、复杂度分析和工程取舍是一道能从小白一路考到资深开发者的经典题。这篇文章围绕“[基础]求素数(质数)”这个主题把从暴力判断到埃氏筛、线性筛再到工程上的大数素性检测和分段筛完整讲一遍。适合刚开始学编程、正在准备面试或者用了很久素数却不太清楚底层原理的朋友。1. 题目拆解考点从来不只是“能跑出结果”1.1 素数定义的边界陷阱我们先从最基本的定义说起。素数是大于1的自然数中除了1和它本身以外不再有其他因数的数。注意“大于1”这个前提所以0和1都不是素数。2是最小的素数同时也是唯一的偶素数——这个性质很重要后面很多优化都建立在“除2以外所有素数都是奇数”这个事实上。很多新手第一次写判断素数时代码长这样def is_prime(n): for i in range(2, n): if n % i 0: return False return True这段代码逻辑没错但有两个问题第一当n0或n1时循环不执行函数会错误地返回True第二当n2时循环也不执行返回True是正确的但判断流程不够严谨。正确的处理应该是先把小于2的情况直接排除再进入循环判断。边界条件这种东西平时觉得无所谓真正到了线上环境或者面试手写代码时漏掉一个边界可能就是零分。我见过不少候选人能流畅说出“从2循环到n-1”的思路但一问到n等于0、1、负数怎么处理一下子就卡住了。所以第一个要养成的习惯是拿到任何题目先把边界列出来再写核心逻辑。1.2 为什么只需要检查到平方根暴力循环到n-1的做法时间复杂度是O(n)。当n稍微大一点比如十万、百万效率就惨不忍睹。但神奇的是我们根本不需要检查那么多。原因在于因数的对称性。如果n有一个大于√n的因数a那么必然存在一个小于√n的因数b使得a×bn。换句话说因数总是成对出现的我们只要在[2, √n]范围内找不到任何因数就能确定n是素数。拿36举例因数对是(2,18)、(3,12)、(4,9)只需要检查到6就已经覆盖了所有可能的“小因数”。这个优化直接把时间复杂度降到了O(√n)量级上的变化是巨大的。说个直观感受判断一个100亿级别的数暴力法要执行100亿次取模优化后只需要10万次差了十万倍。这就是为什么面试官特别看重这个优化点——它考察的不是你会不会写循环而是你能不能理解数学性质并应用到代码里。1.3 取模操作的性能认知还有一个隐藏考点是取模运算符%。在大多数编程语言里取模运算比加减乘都要慢因为底层是除法指令。虽然现代CPU对除法的优化已经很好但在高频循环里减少取模次数仍然是值得注意的。不过这里要提醒一句性能优化要放在正确性之后。如果判断大数的正确性都没把握先别琢磨取模快慢的问题。先把逻辑写对再用性能工具分析最后才是细节优化。这个顺序千万别搞反。2. 从暴力到高效三种常用判断方法2.1 开根号法最简单的正确写法把边界补齐、循环范围缩小到√n就得到了最经典的判断版本import math def is_prime(n): if n 2: return False if n 2: return True if n % 2 0: return False limit int(math.sqrt(n)) for i in range(3, limit 1, 2): if n % i 0: return False return True这段代码做了三件事排除小于2的数单独处理n2排除偶数后只检查从3开始的奇数因子。循环步长为2意味着只检查3、5、7、9……这样一下子就少了一半的取模运算。关于平方根的取法很多语言里用int(math.sqrt(n))会有浮点精度问题特别是当n特别大时sqrt的结果可能被四舍五入到不安全的边界值。像C里我一般推荐使用i n / i这种写法既能避免浮点误差又能防止i*i溢出。这个细节在刷题网站上是常见的WA埋点后面问题排查部分会专门展开。2.2 6k±1规律进一步跳过无用因子再往前走一步我们可以利用一个更精细的性质大于3的素数一定落在6的倍数两侧也就是形如6k-1或6k1。注意反过来不成立形如6k±1的数不一定是素数但素数一定符合这个形式。这个结论可以从余数角度理解。任何一个整数n除以6的余数只可能是0、1、2、3、4、5。余数为0、2、3、4时n必然是2或3的倍数不可能是素数余数为1或5时才可能是素数。利用这个规律我们可以把循环步长进一步优化每6个数只检查2个def is_prime(n): if n 2: return False if n in (2, 3): return True if n % 2 0 or n % 3 0: return False i 5 while i * i n: if n % i 0 or n % (i 2) 0: return False i 6 return True这个写法在朴素优化里已经接近极致每轮只做2次取模。实测下来对于中大规模的判断它比“只排除偶数”的版本快三倍左右。当然它的代价是代码可读性稍微下降需要注释解释为什么步长是6。2.3 三种方法的复杂度对比方法时间思路实际效率适用场景暴力循环到n-1O(n)极慢仅用于教学演示循环到√nO(√n)较快单个数字判断6k±1规律O(√n)更快单个数字判断的进阶版要说工程实践里的选择我个人的习惯是单个数判断直接上6k±1版本代码不长性能也够打批量场景则用后面要讲的埃氏筛。简单问题用简单方法但前提是你得先知道复杂方法在哪里否则等遇到性能瓶颈才去查资料就有点被动了。3. 批量筛选从判断到生成3.1 一个个判断为什么不行如果题目从“判断n是否为素数”升级成“求出n以内的所有素数”还一个一个用上面的方法去查总复杂度是O(n√n)。n取到100万时要做大约10亿次取模运算程序会明显卡顿。这时候就需要换思路。我们不再问“这个数是不是素数”而是反过来主动标记出所有的合数剩下的自然就是素数。这就是埃拉托斯特尼筛法简称埃氏筛一个两千多年前就被发明的算法。3.2 埃氏筛的核心过程埃氏筛的步骤非常直白。从2开始把2的所有倍数4、6、8……全部标记为合数然后找到下一个未标记的数3把3的所有倍数6、9、12……标记为合数再找到下一个未标记的数5……依次类推直到处理完所有不超过√n的数。代码实现大概是这样的def sieve_of_eratosthenes(n): is_prime [True] * (n 1) is_prime[0] is_prime[1] False i 2 while i * i n: if is_prime[i]: for j in range(i * i, n 1, i): is_prime[j] False i 1 return [x for x in range(2, n 1) if is_prime[x]]注意内层循环的起点是i×i不是2×i。原因是i的较小倍数比如2i、3i……直到(i-1)i在此之前已经被更小的质因子标记过了没必要重复标记。这个细节既减少了循环次数也避免了无意义的重复写入。埃氏筛的时间复杂度是O(n log log n)空间复杂度是O(n)。实际跑起来筛100万以内的素数只需要几毫秒筛1亿以内的素数大概在几百毫秒量级非常快。3.3 线性筛让每个合数只被标记一次埃氏筛有一个小瑕疵某些合数会被标记多次。比如12会被2标记一次被3标记一次。重复标记虽然不影响正确性但浪费了时间。于是就有了欧拉筛也叫线性筛核心思路是保证每个合数只被它的最小质因子筛掉一次。线性筛的代码比埃氏筛复杂一些def linear_sieve(n): is_prime [True] * (n 1) primes [] for i in range(2, n 1): 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这里最关键的一行是if i % p 0: break。它的意思是当p能整除i时p已经是i的最小质因子那么i×p的最小质因子也就定下来了。后面更大的质因子p乘上i得到的合数i×p的最小质因子会是p应该在后续某个更合适的时机被筛掉所以现在必须停下来。这行代码是整个线性筛的灵魂很多人第一次看到都会懵。我不要求初学者完全理解它但建议把这段代码背下来在编辑器里手动跑几个例子观察哪些合数在什么时候被标记。理解了它你对“最小质因子”这个数论概念的理解会上升一个台阶。从工程角度看如果只是筛1000万以内的素数埃氏筛和线性筛的差距并不明显。线性筛的优势在n特别大、或者需要在筛的过程中额外维护某些数论函数时才真正体现。所以我的建议是先掌握埃氏筛把线性筛作为进阶储备。4. 特殊场景与进阶玩法4.1 大数的概率性素性检测前面所有方法的天花板都在O(√n)当n是一个几十位的大数时√n本身就可能是个天文数字开根号检测完全不可行。但现实世界确实需要判断超大素数的场景比如现代密码学里生成密钥就要用到几百位的大素数。这类问题不能靠确定性试除而是用概率性素性检测算法最有名的是Miller-Rabin测试。它的核心思想是利用费马小定理的推广形式对一个候选数进行多轮随机基底测试。每一轮如果没通过可以确定它是合数如果通过了只能说“它大概率是素数”。当进行足够多轮测试后误判概率可以降到比硬件随机故障还低。Miller-Rabin的数学原理牵扯到模幂运算和二次探测定理这篇文章不展开但我想强调一个工程点在判断大数素性时用确定性基组合的Miller-Rabin比单纯依赖概率更可靠。例如在32位整数范围内只要用{2, 7, 61}这三个基做测试结果就是确定性的在64位范围内用特定的基集合也能做到完全确定。这段经验是我在实现某个加密协议时踩坑总结出来的光用随机基底其实有极小概率出错虽然概率低但密码学里没人敢赌这个。4.2 分段筛内存不够时的救命稻草埃氏筛需要O(n)的数组当n是10的12次方时就算每个元素只占1字节也需要1TB内存直接爆掉。分段筛的思路是要筛出[2, n]的素数只需要先用常规筛法筛出√n以内的素数然后用这些素数去筛区间[n1, n2]内的合数分批次处理。假设我们要筛出10的12次方到10的12次方100万之间的素数流程是先用埃氏筛筛出10的6次方以内的所有素数用这些素数去标记区间内的合数区间内存数组只需要容纳100万1个元素分段筛在竞赛编程和科研计算里非常常用它把“大范围素数”问题转化为“大范围区间筛”问题内存可控速度也快。个人经验是只要区间长度在千万级别以内分段筛完全可以在普通笔记本上跑出结果。4.3 素数在工程中的实用场景除了数学题和面试题素数在工程里其实无处不在。哈希表设计中桶的数量经常取素数因为素数可以让哈希值均匀分布减少碰撞随机数生成器里不同质数参数的组合能生成周期更长的序列RSA等加密算法直接建立在大素数分解困难这个前提下。我自己在实际项目里用素数最多的地方是动态规划的滚动数组优化用素数取模来分散数据还有数据校验场景里用素数作为位运算掩码的种子能有效避免规律性数据带来的冲突。坦白讲这些应用不是多么高深但它们提醒我们素数不是一个“考试专用”的知识点而是计算机系统里潜藏的数学骨架。5. 常见问题与排查技巧实录5.1 边界漏判数组越界和虚假结果这是我见过的初学者最常见的错误。写判断单个数的代码时忘记处理n0、n1的情况写筛法时忘记把0和1的位置设为False导致筛出来的“素数列表”里混进两个明显不合法的数。排查这类问题没什么捷径唯一的办法是把边界情况整理成一张测试清单。我的习惯是写完任何素数相关代码立刻跑一组固定测试0、1、2、3、4、5、9、15、17、25、97。如果这些数全部判断正确边界基本就没问题了。这个测试清单我用了很多年几乎每次都能抓住问题。5.2 整数溢出平方根判断的隐形杀手在C、C、Java这类语言里i * i n这个写法藏着溢出炸弹。假设n是int类型最大值约21亿当i逼近46340时i的平方已经开始接近int上限。一旦i超过46340i×i直接溢出变成负数循环条件瞬间变成false提前终止于是很多合数漏判。正确写法是用除法替代乘法i n / i。这个写法既避免了溢出又不需要sqrt转换性能上完全没有损失。这个坑我见过不止一次包括一些工作几年的工程师在review时也没注意到。一句话总结能用除法判断就别用乘法除非你确定不会溢出。5.3 重复标记和无意义遍历用埃氏筛时另一个常见的性能损耗是内层循环的起点没有优化。有些人从2*i开始标记导致大量重复操作。比如i5时10、15、20早就被2和3标记过了再去标记一遍纯属浪费。从i*i开始能直接跳过这些冗余操作。同理外层循环只需要跑到√n不需要跑完整个数组。原因是如果n是合数它一定有一个不大于√n的质因子这个质因子在遍历过程中一定已经出现并且已经把n标记为合数。所以外层循环继续往后走只是在做重复劳动。5.4 性能测试的实用方法如果你不确定自己的筛法效率最简单的方式是在本机做一个基准测试。对n100万、1000万、1亿分别跑一次记录耗时。在我常用的笔记本上埃氏筛筛1亿以内的素数大约是0.3秒左右线性筛也差不多但如果某个实现跑到了5秒以上基本可以断定有逻辑问题比如没有从i*i开始标记或者数组类型过大导致缓存压力。另外一个小建议标记数组用byte或者bitarray而不是bool数组。由于缓存和内存带宽的原因用更紧凑的类型能明显提升大范围筛的性能。在Python里可以用bytearray在C里可以用vectorchar都能在不影响可读性的情况下换取性能收益。5.5 一个实用工具函数最后分享一个我常用的完整工具函数把单数判断、区间筛选和素数列表生成整合在一起方便直接抄作业import math def prime_tools(): def is_prime(n): if n 2: return False if n in (2, 3): return True if n % 2 0 or n % 3 0: return False i 5 while i * i n: if n % i 0 or n % (i 2) 0: return False i 6 return True def sieve(n): if n 2: return [] is_prime bytearray(b\x01) * (n 1) is_prime[0] is_prime[1] 0 i 2 while i * i n: if is_prime[i]: is_prime[i*i:n1:i] b\x00 * (((n - i*i) // i) 1) i 1 return [i for i in range(2, n 1) if is_prime[i]] return is_prime, sieve is_prime, sieve prime_tools()这段Python代码用bytearray优化了内存用切片赋值加速了标记过程。在本地测试筛1千万以内的素数耗时在几十毫秒量级足够应付绝大多数场景。回看这些年写素数相关代码的经历我最大的体会是这个基础题目最考验人的地方不在算法本身而在于处理细节的严谨程度。一个边界条件、一处溢出、一段多余的循环都可能成为bug的源头。很多算法看起来简单真正写对并没有那么容易。如果你正在学习编程建议亲手实现一遍埃氏筛和线性筛把边界案例跑通再把代码的实际性能测量一下。这个过程比看十篇教程都管用。