素数算法详解：从试除法到线性筛，避开这些坑

素数这玩意儿大学课本里三行定义实际写起来三天三夜都不一定写得干净。作为“动手学算法”系列的第04篇这篇我打算把素数的判断、生成、进阶证明和几个容易踩的坑一次性捋清楚。不管你是为了面试刷题还是做密码学相关开发哪怕是LabVIEW这类图形化环境里做课设应该都能在里面找到能直接抄的答案。先把话说透素数是数论的地基也是最容易被表面简单骗到的题目。很多人觉得“判断素数不就是看能不能被整除吗”实际上当范围变大、数据变多、要求在变高时单纯的上层写法很快就会撞翻车。这篇文章不求词汇华丽只求把每个步骤背后为什么这么做讲明白顺便把搜索热度很高的“分治法求最大元素位置”“纯粹素数”“反素数”这些词怎么跟素数凑到一起的也一并交代清楚。1. 素数是什么先绕开三个最常见的坑1.1 定义边界为什么1和合数总被误判素数定义一句话大于1的自然数只能被1和它自身整除。但实际写代码时这个定义特别容易让新手栽跟头。最典型的例子就是输入1它的因子只有1恰好满足“只能被1和自身整除”的直觉于是不少人把1当成素数返回true。可数学上1不是素数也不是合数为了统一处理函数第一步就应该把小于2的所有数全部挡在外面。另一个隐蔽的坑是平方数。比如25因子5和5是一对判断范围只需要到√255。如果循环写成i sqrt(n)i最多跑到425的因子5就会被漏掉于是25被误判成素数。这种错误不会在10、21这种数上暴露专门咬平方数排查起来特别讨厌。还有负数负数没有素数的概念但如果你不提前过滤n % i照样能算结果毫无意义。所以我在写判断函数的时候边界条件永远是if (n 2) return false;这一行挡掉的不只是1还有0和负数。1.2 试除法的原理与C语言实现试除法的核心依据是一条数学性质如果n是合数那么它一定有一个因子a满足2≤a≤√n。原因是因子成对出现na×b不可能a和b都大于√n否则乘积就超过n了。所以判断n是不是素数只需要把从2到√n的所有整数试一遍任何一个能整除n它就是合数。这样一来时间复杂度从O(n)直接降到O(√n)单个数判断在n小于10^12时都很轻松。可以用C语言写一个干净的版本int is_prime(int n) { if (n 2) return 0; for (int i 2; i n / i; i) { if (n % i 0) return 0; } return 1; }注意我这里写的是i n / i不是i sqrt(n)。原因有两个第一每次循环都调sqrt会有浮点开销虽然编译器可能优化但没必要赌第二浮点数有精度问题当n大到一定程度sqrt(n)的结果可能被舍入成略小于真实值的数导致i漏掉临界因子。n / i是纯整数除法稳得很。这个写法在大数判断时能避开很多莫名其妙的bug。1.3 6k±1步进用数学规律把速度再提三倍试除法虽然直观但还可以更聪明。观察所有大于3的素数它们模6的余数只可能是1或5。为什么因为任何整数模6的余数只有0、1、2、3、4、5六种余0是6的倍数余2或4是偶数余3是3的倍数这些都不可能是大于3的素数。只有余1对应6k1和余5对应6k-1还有希望。证明很简单大于3的奇数模6只能是1、3、5其中余3的数能被3整除所以只剩下1和5。这一下就把试除的步长从1拉到了6判断时只需要检查6k-1和6k1两列。Java版本可以这样写public static boolean isPrime(int n) { if (n 2) return false; if (n 2 || n 3) return true; if (n % 2 0 || n % 3 0) return false; for (int i 5; i * i n; i 6) { if (n % i 0 || n % (i 2) 0) return false; } return true; }为什么循环里要同时判断i和i 2因为i从5开始5、11、17、23……是6k-1序列i2是7、13、19、25……是6k1序列。这样一次循环覆盖两个候选数。对于100以内的数来说收益很小但判断一个10^12量级的数时试除次数从√n/2降到√n/3差距是肉眼可见的。注意这个写法必须在前面已经排除了2和3的倍数否则步进规律会失效。2. 批量生成素数埃氏筛和线性筛的选型2.1 埃拉托斯特尼筛法面试最常考的筛法单个判断用试除法没问题但要是让你求1到1000000之间的所有素数再挨个试除就太蠢了。埃氏筛的思路是反过来的从2开始每发现一个素数就把它的所有倍数标记成合数剩下的没被标记过的自然就是素数。用布尔数组composite存标记初始全false。流程很简单i从2走到n如果composite[i]为false说明i是素数然后把i的倍数从i * i开始全部标记成true。为什么要从i*i而不是i*2开始因为2i、3i、4i……这些数在i更小的时候就已经被更小的素数标记过了。比如i5时2×510在i2时已经标记3×515在i3时已经标记4×520也在i2时标记过所以从5×525开始才是有意义的。这个优化能把标记次数省下一大截。埃氏筛的时间复杂度是O(n log log n)在n10^7以内都非常能打。面试时先写这个版本基本不会被挑毛病。2.2 欧拉线性筛为什么它能做到O(n)埃氏筛有个小遗憾一个合数可能被多个素数重复标记。比如12被i2标记一次又被i3标记一次。重复标记不会错但会浪费操作。线性筛欧拉筛的思路是让每个合数只被它的最小质因子标记一次从而把复杂度压到真正的O(n)。Java实现长这样int[] primes new int[n 1]; boolean[] composite new boolean[n 1]; int cnt 0; for (int i 2; i n; i) { if (!composite[i]) { primes[cnt] i; } for (int j 0; j cnt (long) i * primes[j] n; j) { composite[i * primes[j]] true; if (i % primes[j] 0) break; } }关键就是内层循环里那句if (i % primes[j] 0) break;。它的意思是当i能被当前素数primes[j]整除时primes[j]就是i的最小质因子那primes[j]乘以i得到的新合数它的最小质因子也是primes[j]。如果接着用更大的素数去标记比如i4时不用4×312去标记因为12的最小质因子是2它应该留给i6时用2去标记6×212这样才能保证每个合数只被标记一次。这个break是整个算法的灵魂少了它线性筛就退化成埃氏筛的变体。实际工程中线性筛不一定比埃氏筛快很多因为常数项在那里。但线性筛能做到在筛的过程中同时求出每个数的最小质因子这对后续做质因数分解、求欧拉函数、求莫比乌斯函数非常有用。如果你后续要做数论题线性筛是更值得掌握的版本。2.3 分段筛选分治法在素数问题里的真身有时候内存装不下整个数组。比如要求[10^12, 10^12 10^6]区间内的素数你不可能开一个10^12的布尔数组。这时候要用分段筛先筛出√b以内的所有素数再用这批素数去区间内标记合数。为什么只需要√b以内的素数因为区间内任何一个合数n必然有一个因子不超过√n而√n≤√b所以用√b以内的素数就能覆盖所有可能的因子。分段筛的本质就是“大问题切小段小段用同样的方法解决”跟分治法完全是一回事。你会在算法题集里看到“分治法求一个n元素数组中最大元素的位置”那道题的核心是“把数组从中间切开分别递归求左右最大值再合并”。分段筛也是这个套路把长区间切成一段一段每段独立标记最后并起来。很多人搜素数的时候老冒出分治法相关的内容其实不是因为素数跟分治有数学关系而是很多在线练习系统把题目按关卡编号排在同一套资源里搜索引擎就一起带出来了。这个事我在第5节还会展开聊。3. 素数的进阶话题证明、生成元与反素数3.1 无穷多个形如4k3的素数一个经典证明素数的分布是数论里很迷人的话题。证明素数无穷多欧几里得的套路是反证法假设有限把全部素数乘起来再加1构造的新数不能整除任何已知素数所以必有新的素因子。这个思路可以原样搬到“4k3型素数无穷多”的证明上。假设形如4k3的素数只有有限多个记为p1、p2、……、pn。构造N4p1p2…pn-1。注意N也能写成4(p1p2…pn-1)3所以N本身是形如4k3的数。而N除以任意一个pi余数都是-1说明N不被任何一个pi整除。现在看N的质因数分解。大于2的奇质数模4的余数只能是1或3也就是要么4k1型要么4k3型。如果N的所有质因子都是4k1型那么它们乘起来的结果也必须是4k1型因为(4a1)(4b1)4(4abab)1。可N明明≡3(mod 4)矛盾。所以N至少有一个4k3型的质因子。这个质因子不在p1到pn里与“有限多”的前提冲突。因此形如4k3的素数有无穷多个。这个证明最精彩的地方在于N本身不一定是素数甚至可能是很多素数的乘积但我们不需要去算具体是哪些因子只需要利用同余性质证明至少有一个“漏网之鱼”。这种证明思路在密码学里很常见不需要知道一个数的完整分解只需要它的某些性质就能推出决定性结论。3.2 素数的生成元数论里的原根到底指什么“素数的生成元”这个词在不同的场景下指两件完全不同的事得先分辨清楚。一种理解是“生成素数的方法公式”。历史上有人试图找一个只产出素数的公式费马猜过形如2^(2^n)1的费马数前几项3、5、17、257、65537都是素数但到F54294967297欧拉发现它等于641×6700417公式梦碎了。现代工程中生成素数没有确定性的直接公式而是用筛选法生成小素数列表或者随机选大整数再用Miller-Rabin这类概率型素性检测测试。Miller-Rabin不是100%确定但做多轮测试后错误率可以压到比宇宙硬件故障率还低工程上完全可以接受。另一种理解是初等数论里的“原根”英文叫primitive root有时也叫生成元。模素数p如果存在一个整数g使得g的1到p-1次幂模p的结果恰好覆盖1到p-1的所有值那g就是模p的一个原根。举个例子模7取g33^133^223^363^443^553^61刚好是1、2、3、4、5、6所以3是模7的原根。原根在Diffie-Hellman密钥交换协议中非常重要通信双方需要共享一个大素数p和它的一个生成元g才能完成公钥推导。你要是听到有人说“素数的生成元”先看上下文是在讲公式还是在讲原根别鸡同鸭讲。3.3 反素数约数数量竞赛中的“卷王”“反素数”这个名字非常有迷惑性它实际上指的是“高合成数”highly composite number一个数的约数数量大于任何比它小的正整数的约数数量。也就是说它得在“约数数量”这个指标上不断打破纪录。前几个反素数是1、2、4、6、12、24、36、48、60、120、180……看出来没有反素数往往都是合数1因为是空集开局算是约定俗成的起点。比如12它的约数是1、2、3、4、6、12一共6个而1到11的所有数的约数数量都不超过6个所以12进榜。24的约数有8个超过12的6个所以24进榜。越往后新纪录越难破两个相邻反素数之间的间隔会越拉越大。要算“前200反素数”就得从1开始逐个计算约数数量并维护当前最大值。约数数量可以用质因数分解后的指数公式如果n∏p_i^(a_i)那d(n)∏(a_i1)。比如1802^2×3^2×5d(180)3×3×218。反素数在工程上没有太多直接用途但是练手非常好它考验筛法、分解、动态维护最大值而且结果能交叉验证算错了立刻会被打脸。3.4 纯粹素数从高位删到只剩一位仍是素数纯粹素数也叫可左截素数left-truncatable prime的定义是一个素数去掉最高位剩下的数仍然为素数再去掉剩余数的最高位仍是素数直到只剩一位这位也必须是素数。举例来说3797去掉最高位3得到797797是素数再去掉最高位7得到9797是素数再去掉9得到77是素数所以3797是纯粹素数。注意这个定义和英文里的right-truncatable prime正好相反——right-truncatable是从最低位开始删比如7393去掉最低位3得739再去掉9得73再去掉3得7。因为中英混用的时候“左”“右”经常说反这是个很大的坑我在后面第5节细说。想自己搜纯粹素数可以从一位素数{2,3,5,7}出发每次尝试在一个已确认的左截素数前面加一位数字dd的范围只可能是{1,3,7,9}。为什么不能加0、2、4、5、6、8因为新数的最高位如果变成偶数或5整个多位数本身就是合数哪怕去掉最高位后是素数也没用。加入之后判断新数是否素数递归继续。已知十进制下的左截素数总共有4260个右截素数只有83个同时满足两个方向的“双向可截素数”只有15个最大的是73939133。这类题的难点不在概念而在递归设计和素性判断的边界非常适合拿来练综合能力。4. 实战LabVIEW中找出100到200之间的素数4.1 算法建模用循环和求余替代公式判断热搜词里有一个“找出100-200整数中的素数在labview中的连接图”一看就是课程作业。LabVIEW是图形化编程语言很多人第一次接触时被密密麻麻的连线吓到但实际上它的逻辑跟C语言没区别只是把循环和判断画成了框。在LabVIEW里求100到200的素数算法还是那套试除法外层循环遍历100到200内层循环从2遍历到sqrt(i)判断i除以j的余数是否为0。只要发现一次整除就说明i不是素数。画连接图时最关键的是两个循环的嵌套关系外层For Loop负责i内层For Loop负责j。内层循环结束时需要把“是否出现过整除”这个布尔标志传出来。一个常见的做法是内层循环里放一个“余数0”函数输出接一个Or逻辑的移位寄存器j从2跑到i/2把结果累积起来只要有一次为真最终结果就是真。4.2 连接图核心思路与一个踩过的坑具体连线方式我建议这么搭外层For Loop的N设为101循环里用“当前循环迭代次数100”得到实际的i。内层For Loop的N设为i/2因为超过i/2的因子不可能再有成对因子了也可以设成根号i但根号计算在LabVIEW里要用平方根函数。内层循环用移位寄存器初始化为False每次把“i%j0”的结果跟移位寄存器做“或”运算循环结束后如果移位寄存器是False就说明i是素数。这中间有个特别容易出问题的地方如果你用条件端子提前跳出内层循环比如一旦发现整除就停止那循环结束时移位寄存器传出来的值确实是True没问题。但如果你把当前判断结果直接放在循环隧道里那隧道传出来的就是最后一次迭代的值取决于j恰好停在哪个位置结果完全不可靠。正确做法是始终用移位寄存器累积不能靠隧道传中间变量。我给学生改作业时见过好几次这种错误程序跑起来一部分素数丢了一部分合数混进来看到输出里的偶数就知道肯定是隧道用错了。4.3 验证结果与调试技巧100到200之间的素数一共21个按大小排列是101、103、107、109、113、127、131、137、139、149、151、157、163、167、173、179、181、191、193、197、199。这个结果建议你手动核对一遍因为LabVIEW里“索引显示”有时候会偏移一位比如循环从0开始但你写成了“i100”最后数组长度是101容易把200也卷进去。200显然不是素数但如果你只验证个数不看具体值很容易漏掉这种错误。还有一个调试技巧先把外层循环范围从100到200改成10到30看看输出是不是11、13、17、19、23、29这6个素数。如果这个小组测试通过再放回100到200基本不会有大问题。别小看这种缩小范围的排查方式图形化编程里连线一多肉眼找错误极费精力不如设个“小样本验证”的开关来得干脆。5. 常见问题与排查技巧实录5.1 为什么搜素数会搜到分治法求最大元素位置很多人查资料时搜“素数”结果命中一堆“分治法求一个n元素数组中最大元素的位置”第一反应是我搜错了其实没有。这些内容通常来自同一个在线练习资源题目按关卡编号排列比如第1关分治求最大值第2关二分查找第04关素数。搜索引擎按网页标题聚合把整个资源包内容都展示出来了所以你看到的“关联”是题目集层面的不是数学层面的。不过分治法确实在素数问题里有应用场景比如并行统计一个超大区间内的素数个数把区间从中间切成左右两段分别筛出素数数量再合并结果。这个思路和“求最大元素位置”完全同构。那道分治题的经典递归写法长这样int find_max_pos(int a[], int l, int r) { if (l r) return l; int mid (l r) / 2; int left_pos find_max_pos(a, l, mid); int right_pos find_max_pos(a, mid 1, r); return a[left_pos] a[right_pos] ? left_pos : right_pos; }三个要点必须记牢递归出口是区间里只有一个元素比较时要比值但返回的是下标区间划分要用[l,mid]和[mid1,r]不能丢中间元素也不能用[l,mid-1]造成元素丢失。这些点跟素数关系不大但对于正在闯关做题的人来说比记素数本身更重要。5.2 判断素数时最隐蔽的几个坑我整理了一份踩坑速查表都是实际跑代码时见过的问题坑位错误写法正确写法后果平方数漏判i sqrt(n)i n / i或i*i n25被误判为素数int溢出i * i nn接近int上限转long long或i n / ii*i溢出成负数循环条件失效过滤不彻底只判断n1if (n 2) return false0和负数被当成素数重复标记埃氏筛从i*2开始从i*i开始效率降低大量重复标记其中平方数漏判是我见过最多的一种。25、49、121这种数因子是成对的但如果你在循环条件里漏了等号就会跟真正的质因子擦肩而过。还有个进阶版的坑判断上亿的大数时有些同学喜欢用int存i*i结果溢出成负数循环直接不执行函数返回true把一堆合数当素数输出。这种bug不会出现在小数据测试里必须用大边界值专门测一下。5.3 “纯粹素数”翻译歧义与资料核对“纯粹素数”这个叫法在国内并不统一。我见过有的文章管“去掉最高位仍是素数”叫“右截素数”但英文里right-truncatable prime指的是从最低位开始删。说白了中英文里“左”“右”指的是相对数位还是相对阅读方向习惯不一样特别容易搞反。我的经验是查资料时不要只看中文名一定要看它的具体操作定义。只要文章里写了“去掉最高位剩余的数仍是素数”那不管它叫左截还是右截你心里清楚这是指去掉最高位那一种。还有“反素数”也有同样的问题数学社区里约定俗成是highly composite number高合成数但偶尔有业余资料把“不是素数的数”叫反素数那其实是“合数”的通俗说法。真要查论文或者对接算法题建议直接用英文关键词搜索可以省掉很多误解。再说回纯粹素数的搜索因为十进制下左截素数总共才4260个右截素数更少只有83个所以理论上可以暴力递归生成。写代码时要注意递归终止条件是当前数变成一位数且是素数时才算成功。同时要判断的是“去掉最高位后剩下的数”不是“去掉最低位后剩下的数”方向搞反结果就完全不一样。这算是我踩过坑之后特别想提醒的一件事。我个人在做素数相关题目时最深的体会是素数的定义只有一句话但它的算法生态相当庞大。单个数判断用6k±1试除足够批量生成埃氏筛的性价比最高一旦涉及密码学或者数论进阶线性筛、原根、Miller-Rabin这些工具就得随时能用。如果你也是在校生我建议把C语言的试除、Java的线性筛、LabVIEW的循环连接图各写一遍亲手踩一次边界条件的坑比看十篇文章都记得牢。剩下的那些“为什么反素数是高合成数”“为什么左截素数要加1、3、7、9”的问题等代码跑顺之后再去深究思路自然就顺了。