素数不是新鲜话题但每次写代码遇到“判断素数”这种基础问题总有人把简单的东西搞复杂或者反过来把朴素的算法用到性能瓶颈。最近我在整理算法笔记正好把素数这条线从头到尾捋了一遍从定义、判断、数学性质到工程实现和一些有趣的变种纯粹素数、反素数、素数的生成元顺手还处理了一个“分治法求数组最大元素位置”的需求——很多人觉得这和素数没关系但在实际做数据分析时我们经常要先定位一个区间里的最大值然后判断这个最大值是不是素数两个问题就这么自然相遇了。这篇文章适合刚接触算法的新手也适合那些想系统整理素数知识的进阶读者。我会把C语言和Java的实现都贴出来把证明“4k3形素数无穷个”的思路拆开讲清楚再把LabVIEW这种图形化编程里找素数的连接图逻辑也说一下。看完你不仅能写出正确的素数判断代码还能理解每一行代码背后的数学依据。1. 素数的本质与数学基础1.1 什么是素数核心定义素数的定义其实就一句话大于1的自然数除了1和它本身以外不再有其他因数。这里得马上排除数字1因为1有且只有一个正因数不满足“两个不同因数”的要求。最小的素数是2它同时是唯一的偶数素数——这句话是素数判断算法里最重要的优化起点。很多人会误把“奇数”当成“素数”的近似实际上除了2以外所有素数都是奇数。但反过来不成立9、15、21都是奇数却不是素数。我之前帮人调试一个“统计100以内素数个数”的作业他直接把所有奇数都算进去了结果多出来好几个合数。原因就是他没有理解奇数和素数在定义上的本质差异素数关注的是“因数个数”奇数关注的是“是否被2整除”两者完全是两个维度。判断一个数是不是素数最原始的方法就是试除法用2到n-1逐个去除看看有没有能整除的。这种方法的时间复杂度是O(n)对于一个100万量级的数字来说要循环接近100万次虽然现代计算机性能很强但如果是批量判断或者是写在嵌入式芯片上这种写法很快就会被淘汰。我们后面要讲的优化方法都是围绕“能不能少试几次”展开的。1.2 素数的几个重要性质含4k3素数无穷的证明思路素数在自然数里的分布看起来毫无规律但几个经典性质是必须记住的它们是很多算法和数学证明的基石。第一素数是无穷多的。欧几里得的证明方法非常经典假设素数有限把它们全部乘起来再加1得到的新数要么本身是素数要么存在一个之前没列出的素因子这产生了矛盾。这个思路可以用在证明“形如4k3的素数有无穷多个”上但需要换个角度。第二形如4k3的素数有无穷多个。这个证明比欧几里得证法复杂一些关键点在于构造反证。我先说结论假设4k3形式的素数只有有限个把它们记为p1, p2, ..., pn。我构造一个数N 4 * (p1 * p2 * ... * pn) - 1也就是N ≡ 3 (mod 4)。这个N一定大于1所以它肯定有素因子。注意任何素数可以写成4m1或者4m3的形式。如果N的所有素因子都是4m1的形式那么这些素因子的乘积也一定是4m1的形式因为两个4m1型的数相乘结果还是4m1但N是4m3型矛盾。所以N至少有一个因子是4m3型的素数而这个因子不可能是p1到pn中的任何一个因为p1到pn都不能整除NN模它们都等于-1。于是我们找到了一个不在假设列表中的4k3型素数矛盾成立。第三如果p是素数那么对于任意整数ap能整除a^(p-1)-1费马小定理。这为后面的“素数生成元”和某些素数判断算法提供了理论支持但注意费马小定理的逆命题不成立直接用逆命题判断素数是危险的这点我在后面的工程实现里会再提。2. 素数判断从数学到代码2.1 朴素判断法与优化原理原始试除法虽然慢但思路直接适合在面试或考试中体现基础。判断一个数n是否为素数只需要从2试到√n。为什么到根号n就够了因为如果n有大于√n的因子d那么n/d一定是小于√n的因子两个因子成对出现。换句话说只要在2到√n之间找不到因子那么n就是素数。这个优化把时间复杂度从O(n)降到了O(√n)看起来只改进了一步实际效果却非常大。判断999983这种六位数原来需要循环近100万次现在最多循环1000次就出结果。再进一步我们可以跳过所有偶数从3开始每次加2只检查奇数因子。这是因为偶数因子只有在n是偶数时才会出现而偶数且大于2不可能是素数。这个优化的代码量增加不多但循环次数又减半。更激进的优化是提前测试2、3和5然后用6k±1的规律步进因为所有大于3的素数都分布在6的倍数附近。这一步的原理是任意整数可以写成6k、6k1、6k2、6k3、6k4、6k5其中6k、6k2、6k3、6k4都是合数除了少数小值只有6k1和6k5即6k-1才可能是素数。所以试除时只需取形如6k±1的数效率更高。需要注意的是这些优化都是针对单个数判断的。如果是判断一个区间内的所有素数最优策略不是逐个判断而是用筛法这个我在第5章会专门讲。2.2 C语言实现与细节解析C语言实现素数判断我给了个兼顾简洁和效率的版本。你写完以后可以自己跑一下感受一下差异。#include stdio.h #include math.h int is_prime(int n) { if (n 2) return 0; if (n 2) return 1; if (n % 2 0) return 0; int limit (int)sqrt(n); for (int i 3; i limit; i 2) { if (n % i 0) return 0; } return 1; } int main() { for (int i 100; i 200; i) { if (is_prime(i)) { printf(%d , i); } } printf(\n); return 0; }这段代码注意几个细节一是sqrt(n)要强制转换成int因为浮点数和int比较容易带来精度问题我在实践中更倾向于用i * i n来循环条件省去开方运算也避免浮点误差二是循环里i 2跳过了所有偶数因为我们已经提前排除了n是偶数的情况。如果你用i也能得出正确结果但循环次数多了一倍。对于n 25这个例子根号下n等于5循环到5时发现25能整除5正确返回0对于n 17根号下n是4循环只有i33不能整除17退出循环返回1。整个流程和数学推导完全吻合。2.3 Java实现与工程化写法Java里判断素数的逻辑和C语言完全一样但工程上我们往往会把它封装成一个静态工具方法并加上一些边界处理。另外Java的BigInteger类有isProbablePrime方法它基于米勒-拉宾算法适合处理大整数的素性检测。如果业务里只需要判断int范围内的数手写方法效率更高因为BigInteger的初始化代价相对较大。下面是我常用的Java版本public final class PrimeUtils { private PrimeUtils() {} public static boolean isPrime(int n) { if (n 2) return false; if (n 2) return true; if ((n 1) 0) return false; for (int i 3; i * i n; i 2) { if (n % i 0) return false; } return true; } public static void main(String[] args) { // 找出100到200之间的素数 for (int i 100; i 200; i) { if (isPrime(i)) { System.out.print(i ); } } } }这段代码里的(n 1) 0是位运算判断偶数位运算比取模稍快一点在高频调用场景下有意义。i * i n避免了Math.sqrt的开销和浮点转换是推荐写法。唯一要注意的是当n很大时i * i可能溢出int范围这时要么把i声明为long要么在大数据场景下直接用BigInteger。我还试过给isPrime加一个long类型的重载方法内部循环变量用long这样判断十亿级别的数字也不怕溢出。如果你的系统需要频繁判断素数建议把这段代码放到一个公共工具类里并配合“小素数表预判”优化先预先算出100以内的所有素数作为试除因子这样前几次试除可以跳过大量合数因子实测性能提升明显。3. 素数相关的经典题目与算法变式3.1 找出100-200整数中的素数含LabVIEW连接图逻辑这是一道很经典的编程题在C语言、Java教程里都有甚至有人问我LabVIEW怎么画。LabVIEW是图形化编程语言它没有for循环的文本写法而是用框图节点。核心逻辑仍然不变外层循环从100循环到200内层循环从2到根号下当前数框图里用一个“商与余数”节点判断余数是否为0再用“小于等于”和“且”逻辑组合成布尔输出。我简单说一下LabVIEW里的连线思路把外层循环的索引i加100作为当前被判断数内层循环的索引j加2作为除数除法节点输出余数和0比较得到的布尔值取反作为“是素数”的候选条件内层循环持续到j*j i才结束如果整个内层循环都没有触发余数为0的事件就把i标为素数并输出。这个程序跑起来100到200之间的素数都能正确显示但如果想在LabVIEW里追求效率可以用“单周期循环”结构把内层循环的次数预先算好避免每次动态判断。我见过很多学生在这里犯的错误是把内层循环的退出条件写成了j i导致循环次数没被根号缩小还有人在框图里忘掉“外层循环在找到第一个因子后立即停止”结果一旦发现合数还在继续算白白浪费性能。图形化编程虽然门槛低但背后的算法优化逻辑一样不少思路清晰比拖拽节点更重要。3.2 纯粹素数不断去掉最高位的素数纯粹素数right-truncatable prime的定义是一个素数去掉最高位后剩下的数仍然为素数再去掉剩下的数的最高位余数还是素数直到剩下一位数这个数本身也是素数。用例子说明2393是素数去掉最高位2得到393393不是素数所以2393不是纯粹素数。而3797是素数去掉最高位3得到797797是素数再去掉7得到9797是素数去掉9得到77是素数所以3797是纯粹素数。注意方向这里说的是“去掉最高位”和常见的“截尾素数”去掉最低位方向相反判断时的递归逻辑也要相应改变。纯粹素数在枚举时有一个很漂亮的思路不直接枚举所有大素数再逐个判断而是利用其构造性质。因为一个n位的纯粹素数它的前n-1位去掉最高位以后必然是一个更小的纯粹素数。所以可以从一位素数2、3、5、7出发每次在末尾追加数字0到9然后判断追加后的数是不是素数如果是就继续追加。这个过程就像树木生长只需要在很小的候选空间内查找。实际数据中三位纯粹素数有15个四位只有8个越往上越稀疏。3.3 反素数拥有最多因数的数“反素数”不是“反着的素数”而是指在某个正整数的范围内因数个数最多的那个数。更严格的定义是对于任意正整数m n如果n的因数个数不少于m的因数个数那么n是一个反素数。比如1到10范围内6有4个因数1、2、3、6比10以内的任何数都多所以6是反素数。前几个反素数是1、2、4、6、12、24、36、48、60、120……这个数列也叫高度合成数。反素数在算法题里经常出现比如“求1到n中因数个数最多的数”。这类题目表面上是素数问题其实更考验因数分解和搜索剪枝。我处理过一个“前200反素数”的枚举需求用DFS依次尝试以2、3、5等素数作为底的指数组合同时记录当前因子总数。由于因数个数公式σ ∏(指数1)只依赖于分解指数所以只需要枚举指数组合而不需要真正分解每一个数字。这个做法在大n比如10^9时依然可以高效运行。3.4 素数的生成元与互素“素数的生成元”这个概念最早来自数论中的模运算。在模pp是素数的意义下存在某些整数g使得g、g^2、g^3、...、g^(p-1)在模p下恰好等于1到p-1的所有值这样的g称为模p的原根。原根当然不只有一个1到p-1中大约有φ(p-1)个原根φ是欧拉函数。原根在密码学里至关重要因为很多加密算法需要生成一个循环群。寻找原根的方法一般是先把p-1分解质因数得到它的全部素因子q1, q2, ..., qk然后从2开始逐个尝试g如果对于每个qig^((p-1)/qi) mod p都不等于1那么g就是原根。这个判定逻辑的背后是拉格朗日定理如果g不是原根它的阶一定是(p-1)的真因子而这个因子一定能被某个qi整除。例如p7p-16质因子是2和3。从g2开始2^3 mod 7 1不满足条件2不是原根试g33^3 mod 7 6 ≠ 13^2 mod 7 2 ≠ 1所以3是7的原根。如果你把“生成元”这个词放到编程语境里另一种理解是素数序列生成器——比如用埃拉托色尼筛生成100万以内的所有素数这也叫素数的生成。这块内容我放到第5章讲筛选法但核心强调的是生成一串素数的思路和判断单个素数不一样不要用isPrime循环扫一万个数应该批量筛查。4. 分治法在数组最大元素位置中的应用与素数判断的联动4.1 分治法求一个n元素数组中最大元素的位置分治法Divide and Conquer的核心思想是把大问题拆成小问题分别求解再合并结果。求一个n元素数组中最大元素的位置教科书上给了一个经典写法把数组从中间一分为二分别递归求出左半部分和右半部分的最大值位置然后比较两个位置上的值返回更大值所在的位置。这个算法的复杂度是O(n)因为每个元素都被访问一次递归深度是O(log n)。我第一次实际使用分治法是在一个历史数据回测任务里我需要在一段连续的交易数据里找到涨幅最大的峰值位置数据量不大但需要多次重复查询。最开始我直接用线性扫描代码简单但后来要和另一个并行计算任务融合分治法天然支持“左半边和右半边分别在不同线程里算”于是我把线性扫描换成了分治。分治的代码我写了个C语言版本方便你直接看递归结构int findMaxPosition(int arr[], int left, int right) { if (left right) return left; int mid left (right - left) / 2; int leftPos findMaxPosition(arr, left, mid); int rightPos findMaxPosition(arr, mid 1, right); return arr[leftPos] arr[rightPos] ? leftPos : rightPos; }注意这里的mid left (right - left) / 2而不是(left right) / 2因为后者在left和right都很大的时候可能溢出。这段代码里没有显式的合并步骤因为返回值本身就是一个位置索引递归返回时用三元运算符就完成了合并。如果你还需要返回最大值本身那么再增加一个变量或者写一个返回值写法即可。4.2 分治法与素数判断的联动场景把分治法求最大值和素数判断放在一起常见于这类需求“找出数组中的最大值并判断它是否为素数”。精简做法是先线性扫描或者分治找到最大值然后调用isPrime判断。但我实际优化过一个并发版本在分治递归的每一层同时比较左右两个子数组中“值最大且素数优先级最高”的元素从而一次性返回“区间内最大的素数及其位置”。因为素数判断本身有代价如果先求全局最大值再判断这个最大值不是素数你还得重新找次大值这样来回跑很多趟。这个联动的具体场景是我做过的一个数据分析工具输入一个传感器数值序列系统需要标出序列中的波峰位置并且判断这个波峰对应的数值是不是质数因为下游的加密模块只认质数标记。我采用分治函数返回一个结构体里面包含“当前区间内最大的素数”和“当前区间内最大的合数”分别记录值和位置递归合并时优先保留素数如果两边都是素数就保留数值更大的否则保留路径上更大的值。这样一次递归结束后直接就能拿到“最大素数及其位置”不需要二次遍历。分治在平均效率上并不会比线性快但它在可扩展性和并行化方面有天然优势。如果你的数据量是几百万级别并且分布在多台机器的内存中分治的“分配-汇总”结构很容易映射到并行框架里。我建议初级程序员先熟练掌握线性扫描再学分治因为分治的递归边界条件很容易写错最容易错的就是区间为空的判断以及mid取整方向不一致导致的死循环。5. 筛法与素数表生成工程实践中的批量判断5.1 埃氏筛与欧拉筛的对比要判断100到200之间的素数用上一章的isPrime循环逐个试除也能算但如果是判断1到100万之间的所有素数再逐个数试除就会等到天荒地老。正确做法是筛法——一次性生成整个区间内的素数表。最经典的筛法是埃拉托斯特尼筛法埃氏筛。从2开始把2的倍数全部标记为合数然后找到下一个未被标记的数3把3的倍数全部标记接着是5、7……直到当前数的平方大于区间上限。你用草稿纸手动模拟一遍1到30的筛选就能理解为什么标记完7以后11的倍数不用再管——因为11乘2、乘3、乘4这些组合在之前已经被更小的素数处理过了。欧拉筛线性筛是埃氏筛的改进它保证每个合数只会被它的最小质因数标记一次时间复杂度严格为O(n)。欧拉筛的核心代码在Java里是这样public static ListInteger linearSieve(int n) { boolean[] isComposite new boolean[n 1]; ListInteger primes new ArrayList(); for (int i 2; i n; i) { if (!isComposite[i]) { primes.add(i); } for (int j 0; j primes.size() i * primes.get(j) n; j) { isComposite[i * primes.get(j)] true; if (i % primes.get(j) 0) { break; } } } return primes; }很多初学者看不懂最后那个break条件i % primes.get(j) 0。我打个比方就像你在餐桌旁依次坐下每个人都只和“最小的朋友”握手就离席这样可以避免重复握手。具体来说当i是primes.get(j)的倍数时更小的那个质因子已经在处理i了如果继续标记i * primes.get(j1)这个合数将来会被primes.get(j)再标记一次造成重复。欧拉筛的代码很短但这个跳出的时机是整个算法的精髓。5.2 基于筛法生成素数表及性能调优我有一份工程经验直接分享给你构造1亿以内的素数表用埃氏筛约需1.5秒欧拉筛约需2秒Java普通笔记本差距并不明显因为两者的常数因素差异不大。但如果你要频繁查询我更推荐直接用BitSet来存储合数标记而不是boolean[]因为BitSet占用内存少八倍数据量大的时候GC造成的卡顿会少很多。还有一个常见的优化是只筛奇数把偶数全部跳过。因为除了2以外所有偶数都不是素数所以可以把数组下标映射成“奇数序号”把空间再砍半。这个优化在嵌入式环境或老机器上很实用。另外在筛选过程中我们从i * i开始标记而不是从2 * i开始因为更小的倍数已经被更小的素数筛过。同样是基于数学上的“成对因子”原理和判断单个素数的优化出发点完全一致。筛法生成素数表后可以做很多事情打表预判断、累加素数前缀和、查找相邻素数差等等。比如要判断几千万个随机大数是否为素数可以把小素数表当作试除的“预检器”先用这些素数快速排除掉大部分合数剩下的再用米勒-拉宾做精确判断。这套组合拳在实战里非常常见。6. 工程排坑经验与性能陷阱6.1 isPrime函数常见错误一览我见过太多人在素数判断代码里栽跟头这里把高频问题整理成一个速查表你写代码时可以先自检一遍。常见错误后果正确写法把1判断为素数结果错误n 2 直接返回false忘记单独处理2偶数全部被拒先判断n 2再排除偶数循环条件写成 i n / 2效率低用 i * i n最多到√n使用sqrt后丢失精度极端情况下漏判因子用整数乘法替代在循环中重复调用sqrt性能浪费提前计算limit变量用费马小定理直接判断可能被卡迈克尔数骗过配合多个底数做米勒-拉宾最后一条我多说一句费马小定理说“如果p是素数则a^(p-1)≡1 mod p”但反过来并不成立。有一些非常稀有的合数比如561、1105、1729对于所有与它们互素的a都满足这个条件它们被称为卡迈克尔数。如果你把费马小定理的逆命题当作判断方法就会把这类合数误判为素数。生产环境里判断大数素数要么用扩展的米勒-拉宾算法要么用Java的BigInteger.isProbablePrime它是工程上的标准方案。6.2 算法选择单点判断、区间枚举与大规模筛选我打个比方查看一个人是不是名人你可以直接调查他个人也可以查一份名人录。单次判断就是前者区间枚举和大规模筛选就是后者。当你要判断“100到200之间的素数”数据范围只有101个数用逐个判断完全没问题但当你要统计“100万以内有多少个素数”再逐个判断就太慢了应该直接筛。我在项目里整理过一张选型提示你可以收藏判断单个int范围内的数手写isPrime循环到√n。判断多个分散的大数比如几十个10^16级别的数先用小素数表试除预筛再用米勒-拉宾。统计较大区间内的所有素数用欧拉筛或者埃氏筛。只需要知道某个数附近的素数分布用分段筛避免创建从0到n的完整数组。明确要求返回“最大素数位置”用分治结构同时记录位置和素性标记。选错算法的后果不只是性能差有些极端场景甚至会导致内存溢出。比如你想筛10^9以内的素数如果用boolean[]直接需要1GB内存改用BitSet只需要125MB再配合分段筛每段只筛1MB左右内存压力就完全可控了。我有个朋友在旧机器上跑全量筛选开了数组之后立刻OutOfMemoryError后来改成分段筛才跑通——算法的选择真的是工程生死线。6.3 关于素数的教学与面试建议如果你是在准备面试或者带新人我强烈建议把“纯粹素数”和“反素数”当作练习材料。它们不是考试大纲的内容但能很好地检验你对递归、因数个数公式和剪枝的理解。比如纯粹素数的生成本质上是一棵搜索树你要考虑分支因子的裁剪反素数的求解需要对“指数组合”有清晰的枚举思路。这些比单纯背代码有价值得多。平时我还会让新人手动算一遍“100以内素数表”然后用“6k±1规则”验证。这个过程能帮他们建立数字直觉素数分布的疏密、合数的规律、为什么“素数间隔可以任意大”。我记得有一次在调试数据恢复工具时需要快速判断两堆小文件的ID编码是否是素数当时就靠一张预生成的1000以内素数表配合二分查找直接秒匹配比实时判断快了一个数量级。这个小技巧也分享给你把静态素数表放到常量数组里运行时不计算只查找。7. 写在最后的一点经验我自己在写这些素数相关的代码时最大的体会是数学上的优雅和工程上的实用经常是两回事。比如4k3素数无穷的证明过程让人拍案叫绝但如果你在代码里真去枚举这种素数直接筛一遍保存结果就行根本不用证明。反过来工程里常用的欧拉筛数学原理说穿了就是“每个合数只被最小质因数标记一次”但要把那个break条件写对还是得靠手动模拟几个小例子才能建立手感。另外不要小看那些看起来老掉牙的题目。LabVIEW里画素数判断流程图、C语言里找100到200的素数、Java里封装工具类——我每一轮复习都能从中注意到新的细节比如这次的位运算优化、分治合并时的返回值结构、大数判断的预筛策略。很多生产环境里的性能问题其实就是这些基础点叠加出来的结果。如果你要扩展isPrime到更高性能下一步可以考虑实现米勒-拉宾算法的多底数版本或者研究一下梅森素数的判定。素数这条线的深度远远超出你我的想象我也是踩过几次坑以后才逐渐摸到门槛。希望这篇总结能帮你少走一些弯路写出更高效、更正确的素数相关代码。