判断素数这件事可能是编程里最经典的一道入门题也是水最深的一道题。说它简单是因为只要学过循环的人三行代码就能写出一个能跑的版本说它水深是因为从这三行代码出发你可以一直优化到数论、加密算法甚至量子计算相关的讨论层面。前阵我在优化一个内部工具发现一处判断素数的逻辑跑得异常慢打开源码一看好家伙循环从2直接除到n减1一次漏网之鱼都没有。这篇文章就把素数判断这件事从暴力到工程级方案整个捋一遍适合刚接触编程的初学者也适合那些已经写了几年代码、但从未认真想过判断素数到底有多少种玩法的开发者。1. 素数判断的本质从数学定义到第一版实现1.1 教科书定义里藏着的两个边界我们先回到最基础的定义素数也叫质数指的是大于1的自然数中除了1和它本身以外不再有其他因数的数。这个定义听起来很简单但里面藏着两个特别容易被忽略的边界。第一个边界是数字1。1既不是素数也不是合数这是一个单独的分类。很多人写判断素数的函数时输入1有时返回true有时返回false完全取决于循环怎么写的。严格来说1单独作为边界处理不要让它混进素数的判定逻辑里。第二个边界是数字2。2是最小的素数也是唯一的偶素数。这个特性决定了我们后面所有优化方案里2和偶数必须单独处理的原因——一旦把2放进去很多优化写法会直接翻车。除此之外负数和0根本不需要进入判素逻辑因为素数定义限定了大于1的自然数。函数入口直接排除非正数就行。1.2 所有算法的起跑线暴力试除实现最朴素的实现思路是既然素数的定义是没有其他因数那我就从2一直尝试除到n-1如果中间任何一个数能整除n就说明它不是素数。代码如下def is_prime(n: int) - bool: if n 2: return False for i in range(2, n): if n % i 0: return False return True这段代码没有任何问题逻辑完全正确但它的时间复杂度是O(n)。如果n是1万循环1万次如果n是1个亿循环1个亿次。这个复杂度在实际项目里是不可接受的。但暴力试除并非一无是处。它是理解一切优化的原点。你只需要想明白一个问题为什么从2循环到n-1有大量的无效操作答案是因数对称性。如果n a × b那么a和b必然一个小于等于√n、另一个大于等于√n。比如28 4 × 74 ≤ √28 ≈ 5.297 ≥ 5.29。也就是说如果你一直检查到了√n还没发现能整除的因子那n就是素数根本不需要继续查下去。这个对称性是所有循环边界优化的理论基础。2. 关键优化链从 sqrt 边界到 6k±1 判别2.1 为什么先优化循环边界而不是循环步长很多人一上来就想着跳过偶数、跳过能被3整除的数但第一步应该做的是把循环边界从n缩到√n。这一步收益最大因为它把复杂度从O(n)直接降到O(√n)。还是刚才的例子判断1亿以内的素数循环到1亿是1亿次循环到1万是1万次差了整整1万倍。这一步都不做后面那些花哨的跳跃步长优化都是在浪费时间。循环条件的写法也有讲究。最直观的是写成i math.isqrt(n)但在某些语言里开方函数可能会引入浮点误差更稳妥的写法是i * i n或者i n // i。用乘法的写法需要小心整数溢出比如在32位int里i一旦超过46340i*i就超过int上限了溢出后反而可能为负循环条件就直接废了。用除法i n / i最安全就是每次循环多一次除法运算性能略损但换来了绝对正确。优化后的代码长这样def is_prime_v1(n: int) - bool: if n 2: return False i 2 while i * i n: if n % i 0: return False i 1 return True2.2 6k±1 判别的数学依据与代码形态边界优化做完之后再回头看看循环内部的1万次迭代你很快会发现很多数根本没必要试除。先排除偶数如果n是偶数且不等于2那它一定是合数。所以第一步判断n是否为2然后再判断n是否为偶数就能直接砍掉一半的迭代量。再往深挖一点除了2和3之外所有素数都满足一个规律——它们都在6的倍数附近即形如6k1或6k-1。为什么因为任何一个整数除以6的余数只有0、1、2、3、4、5这六种。如果余数是0、2、3、4那么这个数分别能被6、2、3、2整除只有余数为1或5的数才可能是素数。而余数为5的数等价于6k-1。这意味着循环时根本不需要逐个检查每个整数只需要检查6k±1形式的数就够了。代码写出来是这样def is_prime_v2(n: int) - bool: if n 3: return n 1 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这段代码的妙处在于i 6之后i和i2正好覆盖了下一组6k±1的位置。举个例子n 49时i从5开始先检查49是否被5整除再检查49是否被7整除第二下就发现了。如果不做这个优化循环要到7才知道答案做了之后循环仍然是7但跳过了6这个不必要的检查点。复杂度从O(√n)进一步降到O(√n/3)。2.3 实测对比不同优化档位的耗时差异我拿n 2147483647这是32位int能表示的最大素数做过一轮简单的对比测试环境是Python 3.10普通PC。结果是暴力试除完全跑不动我按了CtrlC优化到√n边界后大约需要2秒多再用上6k±1的跳跃耗时降到了0.08秒左右。这个差距在单次数值判断上已经足够震撼如果放到循环里批量判断那差距就不是性能问题了是程序能不能在超时时间内跑完的问题。这轮优化做下来你已经掌握了单素数判断最核心的优化套路。如果你的需求只是偶尔判断几个整数到这里就基本够用了。3. 批量判断场景一次性判断海量数字的正确解法3.1 单点优化的天花板单个数字判断无论怎么优化最优也是O(√n)。这在判断一个大数时没问题但如果你的需求是统计1到100万之间有多少个素数或者给出一段区间内所有素数这种批量任务逐个数调用单点判断函数会让CPU流泪。比如1到100万之间每个数都做一次O(√n)判断累计运算量是非常可观的而且其中有大量重复的取模运算。批量场景的正确姿势是筛法。筛法的核心思想很朴素一个合数必然是某个较小素数的倍数那么我们从小到大遍历的时候每遇到一个素数就把它所有的倍数都标记为合数剩下的自然就是素数。3.2 埃拉托斯特尼筛空间换时间的经典套路最经典的筛法是埃拉托斯特尼筛名字听起来陌生做法一点都不神秘。准备一个长度为n1的布尔数组初始全部标记为True假设都是素数。然后从2开始遇到一个True就把它加入素数列表同时把这个数所有的倍数标记为False。因为从2的倍数开始筛4、6、8都会被标记到3的时候6、9、12也会被标记到4的时候发现4早就被标记成False了直接跳过。def sieve_of_eratosthenes(n: int): is_prime [True] * (n 1) is_prime[0] is_prime[1] False for i in range(2, int(n ** 0.5) 1): if is_prime[i]: for j in range(i * i, n 1, i): is_prime[j] False return [i for i in range(n 1) if is_prime[i]]这里有个细节要单独说明j为什么从i * i开始而不是从i * 2开始因为当i5时5×210这个数在i2的时候就已经被筛过了5×315在i3的时候被筛过了5×420在i2的时候被筛过了。所有比i小的素因子组合都已经处理完毕直接从平方开始筛可以跳过大量重复标记。这个细节不仅提升性能也让代码逻辑更干净。复杂度方面埃拉托斯特尼筛的时间复杂度是O(n log log n)空间复杂度O(n)。在处理1千万以内的素数统计时这个方案的表现非常稳定。3.3 欧拉筛每个合数只被筛掉一次埃拉托斯特尼筛有个瑕疵某些合数会被重复标记。比如30它同时是2、3、5的倍数会被标记三次。虽然重复标记不影响正确性但在极大规模下会增加开销。欧拉筛线性筛解决了这个问题。它的思路是每个合数只被它的最小质因子筛掉一次。def linear_sieve(n: int): 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 return primes其中if i % p 0: break这行是关键中的关键。它的含义是一旦当前i能被p整除说明p已经是i的因子那么i × p的最小质因子就是p。如果继续用更大的素数p去乘i得到的新数的最小质因子就不再是p了后续就会产生重复标记。欧拉筛本身并不是什么高不可攀的技巧它就是明白了一件事与其多次标记同一个合数不如花一点额外逻辑确保每个合数只处理一次。实际性能上在10^7量级以内欧拉筛和埃拉托斯特尼筛的差距很小主要是常数层面的差异但了解这个优化思路本身就是值得的。批量筛选的方案选型我的建议是如果n在10^6以内用最简单的埃拉托斯特尼筛就行如果n到了10^7以上用欧拉筛更稳妥如果内存吃紧需要节省空间也可以用分段筛法一次只筛一小段区间但代码复杂度会上一个台阶。4. 五个最容易翻车的隐藏陷阱4.1 边界输入0、1、2和负数我见过太多精心优化的代码在边界输入上翻车。最典型的一个是if n 3: return n 1这行代码看似简短但你要是没想明白就很容易出错。n0时n1为Falsen1时也是Falsen2时是Truen3时是True完全正确。但有些人在这个判断之前又单独写了个if n 2: return False之类的逻辑纯属画蛇添足反而引入了bug。负数的情况也要处理。如果你把n -7传给函数循环判断i * i n根本不成立因为平方永远非负之后函数可能直接返回True把负数判定成素数。这显然错误。所有负数、0、1都应该在函数入口直接返回False。一个统一的写法是if n 2: return False一次性排除掉所有非正数和1。还有一个常见错误是忘记n本身就是完全平方数的场景。比如n49循环到i7时7 * 7 49成立49 % 7 0返回False没问题。但如果你用了i n / i的写法要特别注意整数除法的精度好在7 7是成立的这个问题不大。真正的坑出现在浮点开方那个优化方案里。4.2 乘法溢出与浮点开方的坑前面提过在C/C这类强类型语言里i * i n有一个隐蔽的溢出问题。假设int是32位最大能表示2147483647。当i迭代到46341时i×i已经超过int上限但具体行为是未定义的实际通常表现为溢出成负数一旦i*i变为负数循环条件i * i n永远成立你的程序会从循环到√n退化成循环到n性能瞬间崩盘而且你很难察觉为什么变慢了。稳妥的写法是if i n / i避免了溢出的可能。虽然每次循环多了一次整数除法但换来的是安全。性能敏感的C语言代码里有人会用if (i n / i) break;来判断循环是否该终止原理相同。浮点开方int(sqrt(n))的问题更隐蔽。对某些完全平方数浮点运算可能返回一个略小或略大的近似值比如sqrt(25)理论上应该是5但实现细节可能导致4.999999999999999直接int转型就成了4循环少检查了一轮于是25被误判成素数。当然现代数学库对sqrt的精度控制很好大部分语言里这个问题很少出现但你既然知道有这个坑就不要在自己代码里冒险。Python里有math.isqrt可以直接拿整数平方根完全避开浮点误差这是我目前最推荐的做法。4.3 重复查询场景下的缓存设计还有一个容易被忽视的工程问题同一批数字被反复判断素数怎么办比如你在做一个数学游戏用户会多次提交同一个数字进行检测每次重新从头算一遍显然浪费。解决方案很简单用字典或者哈希表做一层缓存prime_cache {} def is_prime_cached(n: int) - bool: if n in prime_cache: return prime_cache[n] result is_prime_v2(n) prime_cache[n] result return result这种做法的收益在单次调用上看不出来但当你判断100个数字、其中有一半是重复时缓存能省下近一半的重复计算。如果需要缓存的是某个范围内的所有素数那更高效的做法是把范围段存下来比如用分段筛把100万到200万之间的素数先筛一遍缓存好后续所有落在这个区间内的查询都直接查表。缓存不是算法优化但它往往是实际项目里收益最大、见效最快的一笔改动。4.4 误把1当素数、把2排除在外我始终觉得边界处理是最考验程序员细心程度的部分。很多人把代码写成能被2整除且不是2的排除在外时逻辑搞反反而把2给误伤了。写一个判断函数第一件事是测试这几个特殊输入2、3、5、7、11、13这些素数必须返回True0、1、4、6、8、9这些数必须返回False。边界用例全部通过之后这个函数才算真正立住了。5. 再进一步Miller-Rabin 与大数判定的工程选择5.1 试除法的天花板到了这一步你已经掌握了单点判定的全部优化和批量筛法。但还有一个现实问题没有解决如果n是一个大数比如10^12量级甚至更大试除法还可行吗试除法的最优复杂度是O(√n)那么n10^12时需要大约10^6次迭代。这倒不是完全不可接受但如果你做的是加密相关的工作n可能是10^30甚至10^100以上的大整数试除法就彻底没有希望了。大数判定素数的需求在工程领域是真实存在的尤其是RSA一类的加密算法需要生成大素数。这类场景下试除法只能作为早期的廉价筛选手段真正的判定要靠概率性算法。5.2 Miller-Rabin把大概率正确用到极致Miller-Rabin算法基于费马小定理的一个推论。费马小定理说如果p是素数那么对于任何不是p倍数的整数a都有a^(p-1) ≡ 1 (mod p)。反过来如果某个a使得a^(n-1) ≡ 1 (mod n)成立n不一定是素数可能是伪素数。Miller-Rabin就是把这个检测做了多轮通过精心选择的基底把误判率压到足够低。它的核心思路是把n-1分解成2^r × d的形式其中d是奇数然后分步检测幂运算结果。如果某个基底a使所有检测都通过且出现非平凡平方根则n一定是合数如果检测结果为1或-1则通过本轮检测。在实际工程中Miller-Rabin最诱人的地方在于对于32位int范围内的数字只需要用3个固定的基底比如2、7、61进行检测结果就是完全确定的相当于确定性算法。对于64位long范围内的数字用7个基底2、325、9375、28178、450775、9780504、1795265022就足够了。这意味着在常规工程范围内Miller-Rabin不仅是概率算法它实际上是一个快速确定性算法。不同规模数字下的方案选择可以参考这张表数字范围推荐方案说明1万以内埃拉托斯特尼筛或直接试除数据量小怎么算都行10^6以内单个判断6k±1试除法几十微秒级别无需引入额外复杂度10^12以内单个判断预先生成小素数表只试除表内素数只需遍历到√n取整但用素数表跳跃大跳步10^18以内单个判断Miller-Rabin7个基底确定性版本性能远优于试除且结果确定加密级别大数Miller-Rabin 多轮随机基底正确率可达1-4^(-k)取k20以上5.3 工程实践中的一条完整路径综合前面所有内容我在实际项目中最常用的做法是分三层第一层用简单的位运算排除偶数第二层预先生成一个小素数表比如前1000个素数用它们做快速试除因为大部分合数都有很小的因子这一步能过滤掉绝大多数非素数第三层再上Miller-Rabin对剩余的大数做概率性判定。这样组合起来既不缺速度也不缺确定性代码还好维护。说起来判断素数这件事从顶到底其实是一条完整的优化思路链条从理解定义、到边界收缩、再到跳跃步长、然后批量筛法、最后落到大数概率判定。每一层都有对应的应用场景没有哪一层是绝对的最优解。我在实际写代码时会先明确数据的规模上限再决定用哪一层方案——这才是最关键的经验不要为永远不可能出现的大数提前引入不必要的复杂度也不要让即将上线的功能卡在O(n)的暴力循环上。希望这篇文章能帮大家把这条思路链条补完整遇到素数判断的时候心里有数脚下有路。