企业官网建设流程全解析

素数这玩意儿，大学课本里三行定义，实际写起来三天三夜都不一定写得干净。作为“动手学算法”系列的第04篇，这篇我打算把素数的判断、生成、进阶证明和几个容易踩的坑一次性捋清楚。不管你是为了面试刷题，还是做密码学相关开发，哪怕是LabVIEW这类图形化环境里做课设，应该都能在里面找到能直接抄的答案。先把话说透：素数是数论的地基，也是最容易被表面简单骗到的题目。很多人觉得“判断素数不就是看能不能被整除吗”，实际上当范围变大、数据变多、要求在变高时，单纯的上层写法很快就会撞翻车。这篇文章不求词汇华丽，只求把每个步骤背后为什么这么做讲明白，顺便把搜索热度很高的“分治法求最大元素位置”“纯粹素数”“反素数”这些词怎么跟素数凑到一起的，也一并交代清楚。

1. 素数是什么：先绕开三个最常见的坑

1.1 定义边界：为什么1和合数总被误判

素数定义一句话：大于1的自然数，只能被1和它自身整除。但实际写代码时，这个定义特别容易让新手栽跟头。最典型的例子就是输入1：它的因子只有1，恰好满足“只能被1和自身整除”的直觉，于是不少人把1当成素数返回true。可数学上1不是素数也不是合数，为了统一处理，函数第一步就应该把小于2的所有数全部挡在外面。

另一个隐蔽的坑是平方数。比如25，因子5和5是一对，判断范围只需要到√25=5。如果循环写成i < sqrt(n)，i最多跑到4，25的因子5就会被漏掉，于是25被误判成素数。这种错误不会在10、21这种数上暴露，专门咬平方数，排查起来特别讨厌。还有负数：负数没有素数的概念，但如果你不提前过滤，n % i照样能算，结果毫无意义。所以我在写判断函数的时候，边界条件永远是if (n < 2) return false;，这一行挡掉的不只是1，还有0和负数。

1.2 试除法的原理与C语言实现

试除法的核心依据是一条数学性质：如果n是合数，那么它一定有一个因子a满足2≤a≤√n。原因是因子成对出现，n=a×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（对应6k+1）和余5（对应6k-1）还有希望。证明很简单：大于3的奇数模6只能是1、3、5，其中余3的数能被3整除，所以只剩下1和5。这一下就把试除的步长从1拉到了6，判断时只需要检查6k-1和6k+1两列。

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序列；i+2是7、13、19、25……是6k+1序列。这样一次循环覆盖两个候选数。对于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更小的时候就已经被更小的素数标记过了。比如i=5时，2×5=10在i=2时已经标记，3×5=15在i=3时已经标记，4×5=20也在i=2时标记过，所以从5×5=25开始才是有意义的。这个优化能把标记次数省下一大截。埃氏筛的时间复杂度是O(n log log n)，在n=10^7以内都非常能打。面试时先写这个版本，基本不会被挑毛病。

2.2 欧拉线性筛：为什么它能做到O(n)

埃氏筛有个小遗憾：一个合数可能被多个素数重复标记。比如12，被i=2标记一次，又被i=3标记一次。重复标记不会错，但会浪费操作。线性筛（欧拉筛）的思路是：让每个合数只被它的最小质因子标记一次，从而把复杂度压到真正的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]。如果接着用更大的素数去标记，比如i=4时，不用4×3=12去标记，因为12的最小质因子是2，它应该留给i=6时用2去标记（6×2=12），这样才能保证每个合数只被标记一次。这个break是整个算法的灵魂，少了它线性筛就退化成埃氏筛的变体。

实际工程中，线性筛不一定比埃氏筛快很多，因为常数项在那里。但线性筛能做到在筛的过程中同时求出每个数的最小质因子，这对后续做质因数分解、求欧拉函数、求莫比乌斯函数非常有用。如果你后续要做数论题，线性筛是更值得掌握的版本。

2.3 分段筛选：分治法在素数问题里的真身

有时候内存装不下整个数组。比如要求[10^12, 10^12 + 10^6]区间内的素数，你不可能开一个10^12的布尔数组。这时候要用分段筛：先筛出√b以内的所有素数，再用这批素数去区间内标记合数。为什么只需要√b以内的素数？因为区间内任何一个合数n，必然有一个因子不超过√n，而√n≤√b，所以用√b以内的素数就能覆盖所有可能的因子。

分段筛的本质就是“大问题切小段，小段用同样的方法解决”，跟分治法完全是一回事。你会在算法题集里看到“分治法求一个n元素数组中最大元素的位置”，那道题的核心是“把数组从中间切开，分别递归求左右最大值再合并”。分段筛也是这个套路：把长区间切成一段一段，每段独立标记，最后并起来。很多人搜素数的时候老冒出分治法相关的内容，其实不是因为素数跟分治有数学关系，而是很多在线练习系统把题目按关卡编号排在同一套资源里，搜索引擎就一起带出来了。这个事我在第5节还会展开聊。

3. 素数的进阶话题：证明、生成元与反素数

3.1 无穷多个形如4k+3的素数：一个经典证明

素数的分布是数论里很迷人的话题。证明素数无穷多，欧几里得的套路是反证法：假设有限，把全部素数乘起来再加1，构造的新数不能整除任何已知素数，所以必有新的素因子。这个思路可以原样搬到“4k+3型素数无穷多”的证明上。

假设形如4k+3的素数只有有限多个，记为p1、p2、……、pn。构造N=4p1p2…pn-1。注意N也能写成4(p1p2…pn-1)+3，所以N本身是形如4k+3的数。而N除以任意一个pi，余数都是-1，说明N不被任何一个pi整除。现在看N的质因数分解。大于2的奇质数模4的余数只能是1或3，也就是要么4k+1型，要么4k+3型。如果N的所有质因子都是4k+1型，那么它们乘起来的结果也必须是4k+1型，因为(4a+1)(4b+1)=4(4ab+a+b)+1。可N明明≡3(mod 4)，矛盾。所以N至少有一个4k+3型的质因子。这个质因子不在p1到pn里，与“有限多”的前提冲突。因此，形如4k+3的素数有无穷多个。

这个证明最精彩的地方在于：N本身不一定是素数，甚至可能是很多素数的乘积，但我们不需要去算具体是哪些因子，只需要利用同余性质证明至少有一个“漏网之鱼”。这种证明思路在密码学里很常见：不需要知道一个数的完整分解，只需要它的某些性质，就能推出决定性结论。

3.2 素数的生成元：数论里的原根到底指什么

“素数的生成元”这个词在不同的场景下指两件完全不同的事，得先分辨清楚。

一种理解是“生成素数的方法公式”。历史上有人试图找一个只产出素数的公式，费马猜过形如2^(2^n)+1的费马数，前几项3、5、17、257、65537都是素数，但到F5=4294967297，欧拉发现它等于641×6700417，公式梦碎了。现代工程中生成素数没有确定性的直接公式，而是用筛选法生成小素数列表，或者随机选大整数再用Miller-Rabin这类概率型素性检测测试。Miller-Rabin不是100%确定，但做多轮测试后错误率可以压到比宇宙硬件故障率还低，工程上完全可以接受。

另一种理解是初等数论里的“原根”，英文叫primitive root，有时也叫生成元。模素数p，如果存在一个整数g，使得g的1到p-1次幂模p的结果恰好覆盖1到p-1的所有值，那g就是模p的一个原根。举个例子，模7，取g=3：3^1=3，3^2=2，3^3=6，3^4=4，3^5=5，3^6=1，刚好是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_i+1)。比如180=2^2×3^2×5，d(180)=3×3×2=18。反素数在工程上没有太多直接用途，但是练手非常好：它考验筛法、分解、动态维护最大值，而且结果能交叉验证，算错了立刻会被打脸。

3.4 纯粹素数：从高位删到只剩一位仍是素数

纯粹素数（也叫可左截素数，left-truncatable prime）的定义是：一个素数，去掉最高位，剩下的数仍然为素数；再去掉剩余数的最高位，仍是素数，直到只剩一位，这位也必须是素数。

举例来说，3797：去掉最高位3，得到797，797是素数；再去掉最高位7，得到97，97是素数；再去掉9，得到7，7是素数，所以3797是纯粹素数。注意这个定义和英文里的right-truncatable prime正好相反——right-truncatable是从最低位开始删，比如7393去掉最低位3得739，再去掉9得73，再去掉3得7。因为中英混用的时候“左”“右”经常说反，这是个很大的坑，我在后面第5节细说。

想自己搜纯粹素数，可以从一位素数{2,3,5,7}出发，每次尝试在一个已确认的左截素数前面加一位数字d，d的范围只可能是{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%j==0”的结果跟移位寄存器做“或”运算，循环结束后如果移位寄存器是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开始但你写成了“i+100”，最后数组长度是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]和[mid+1,r]，不能丢中间元素，也不能用[l,mid-1]造成元素丢失。这些点跟素数关系不大，但对于正在闯关做题的人来说，比记素数本身更重要。

5.2 判断素数时最隐蔽的几个坑

我整理了一份踩坑速查表，都是实际跑代码时见过的问题：

其中平方数漏判是我见过最多的一种。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”的问题，等代码跑顺之后再去深究，思路自然就顺了。