1. 从一道题说起为什么判定质数值得深究最近在AcWing上刷题又碰到了那道经典的866题——试除法判定质数。题目本身是个模板题要求很简单给定n个正整数对于每个数判断它是否是质数。很多朋友尤其是刚开始接触算法竞赛或者准备面试的朋友可能会觉得这题太基础了不就是写个循环从2除到sqrt(x)吗有什么好讲的我刚开始也是这么想的直到后来在真实的项目开发、性能优化甚至是一些安全相关的场景里反复被“如何高效、正确地判断一个数是否为质数”这个问题“教育”。比如在生成RSA密钥对时需要寻找大质数在一些哈希算法或者随机数生成器的底层质数判断是基础操作甚至在处理一些看似简单的业务逻辑比如给商品分配唯一ID时如果设计不当低效的质数判断也可能成为性能瓶颈。这道题之所以经典正是因为它剥离了复杂的外壳直指算法最核心的两个诉求正确性和效率。而“试除法”作为最直观的解法恰恰是理解这两个诉求的绝佳起点。今天我们就以C实现为例不满足于“AC”这道题而是深挖一下“试除法判定质数”这个操作。我会带你看看最朴素的写法有什么坑如何一步步优化到竞赛和工程中常用的“优化版试除法”并解释清楚每一个优化步骤背后的数学原理和性能考量。你会发现即使是一个for循环里面也大有文章。2. 质数判定的核心理解试除法的本质在动手写代码之前我们必须先搞清楚我们要解决的问题究竟是什么。质数素数的定义是在大于1的自然数中除了1和它自身外不能被其他自然数整除的数。根据定义最直接的判断方法就是“试除”尝试用所有可能的小于它的数去整除它如果都除不尽它就是质数。这个思路对应到算法上就是一个典型的枚举算法。我们枚举所有可能的因子i(从2开始)检查x % i 0是否成立。一旦成立说明找到了一个因子x就不是质数如果枚举完所有可能的i都没有找到因子那么x就是质数。这里立刻引出了第一个关键问题我们需要枚举到多少或者说i的上界是多少一个常见的错误是枚举到x-1。这显然效率极低对于一个大数来说是不可接受的。我们需要利用数学性质来缩小枚举范围。定理如果x是一个合数那么它必定有一个不大于sqrt(x)的质因子。这个定理是试除法优化的基石。我们来简单证明一下假设x是合数那么它可以分解为两个因子a和b即x a * b。不妨设a b。那么a * a a * b x所以a sqrt(x)。也就是说那个较小的因子a一定小于等于x的平方根。因此我们只需要检查从2到sqrt(x)的整数中是否存在x的因子即可。如果在这个范围内都找不到因子那么x就是质数。这就将枚举范围从O(x)缩小到了O(sqrt(x))这是一个巨大的优化。例如判断10^9是否是质数只需要枚举大约31622次而不是10^9次。基于这个理解我们可以写出第一版“朴素试除法”的代码框架bool is_prime(int x) { if (x 2) return false; // 质数定义要求大于1 for (int i 2; i x / i; i) { // 循环条件i sqrt(x) 用 i x/i 避免溢出和浮点数运算 if (x % i 0) return false; } return true; }注意循环条件i x / i。这是一个非常巧妙且安全的写法。它等价于i sqrt(x)但避免了使用sqrt函数带来的浮点数精度问题和可能的性能开销虽然现代编译器优化后差别不大更重要的是它完全在整数域内运算避免了i*i可能导致整数溢出的风险当x接近int最大值时i*i可能会溢出。注意这里有一个初学者极易混淆的点。循环的终止条件是i x / i而不是i x / i。为什么需要等于考虑x4的情况。sqrt(4)2。我们需要检查i2因为4 % 2 0。如果条件是i x/i即i 4/22那么循环根本不会进入i2不会被检查程序会错误地将4判定为质数。所以这个等号至关重要。3. 效率进阶优化枚举的步长上面的代码已经是一个正确的试除法实现了。对于AcWing866这样的模板题输入规模n在100以内每个数x在2^31−1以内这个算法完全够用时间复杂度是O(n * sqrt(x))。但是如果我们追求极致的效率或者x本身非常大我们还能再优化吗答案是肯定的。我们还可以从减少枚举次数上做文章。观察一下我们枚举的序列2, 3, 4, 5, 6, 7, 8, 9, 10, ...。作为一个合数如果它不能被2整除那么它肯定也不能被4、6、8、10等所有偶数整除。换句话说除了2以外所有偶数都不可能是质数因为它们至少有因子2。那么我们在枚举时是不是可以跳过所有的偶数呢这就是第一个优化特判2然后从3开始每次循环步进2i 2只检查奇数。优化后的代码如下bool is_prime(int x) { if (x 2) return false; if (x 2) return true; // 单独判断2 if (x % 2 0) return false; // 排除所有偶数 for (int i 3; i x / i; i 2) { // 从3开始每次加2 if (x % i 0) return false; } return true; }这个优化直接将循环次数减少了一半因为大约一半的整数是偶数我们跳过了它们。这是一个非常可观的性能提升。那么还能更进一步吗可以。我们不仅想跳过偶数还想跳过那些明显不是质因子的数比如3的倍数除了3本身、5的倍数等等。这引出了“6n±1”法则。定理所有大于3的质数都可以表示为6n ± 1的形式n为正整数。简单证明任何一个整数都可以表示为6n, 6n1, 6n2, 6n3, 6n4, 6n5。其中6n能被6整除合数。6n2 2(3n1)能被2整除合数。6n3 3(2n1)能被3整除合数。6n4 2(3n2)能被2整除合数。剩下的只有6n1和6n5即6n-1。因此质数除了2和3一定落在这两种形式中。反之一个数如果是6n±1的形式它不一定是质数比如25 6*41但我们可以利用这个性质来优化枚举我们只需要检查形如6n±1的数是否能整除x即可。基于这个思想的优化版本如下bool is_prime(int x) { if (x 2) return false; if (x 2 || x 3) return true; if (x % 2 0 || x % 3 0) return false; // 排除能被2或3整除的数 // 枚举形如 6n±1 的数i, i2 // 从5开始56*1-1, 76*11, 116*2-1, 136*21 ... for (int i 5; i x / i; i 6) { // 检查 i 和 i2 是否能整除 x if (x % i 0 || x % (i 2) 0) return false; } return true; }这个版本进一步减少了需要检查的除数数量。在sqrt(x)范围内我们大约只需要检查其中1/3的数因为每6个数里我们只检查2个6n-1和6n1。相比最原始的版本理论上循环次数减少了约2/3。实操心得在算法竞赛中对于单次判断通常使用“跳过偶数”的优化就足够了代码更简洁。而在需要反复调用、对性能要求极高的场景例如筛法求质数表中判断一个数是否为质数或者x特别大时“6n±1”优化会更有价值。在实际工程中除非是性能热点否则代码的可读性更重要朴素的i x/i版本往往是首选因为它最清晰不易出错。4. 边界与陷阱代码实现中的魔鬼细节理论很美好但代码落地时魔鬼藏在细节里。试除法虽然简单但写出健壮、无懈可击的代码需要注意以下几个关键点4.1 输入范围与数据类型题目中x的范围是[2, 2^31-1]这正是int型正整数能表示的最大值约21亿。这直接影响了我们代码中的细节循环条件i x / i如前所述这是防止i*i溢出的最佳写法。如果写成i*i x当x很大比如接近21亿i在几万量级时i*i就可能超过int范围导致溢出进而引发未定义行为或错误判断。函数参数类型虽然题目是int但如果我们想写一个更通用的函数考虑x可能更大比如long long范围那么循环变量i和条件判断都需要使用long long类型或者继续采用i x / i这种安全的除法形式。4.2 特殊值的处理这是最容易出错的地方。小于2的数根据定义质数必须大于1。所以x 2时要直接返回false。这包括了0,1和所有负数。等于2的数2是最小的质数也是唯一的偶质数。在“跳过偶数”的优化版本中必须对x 2进行特判否则它会被if (x % 2 0)排除掉。等于3的数在“6n±1”优化版本中3也需要特判因为它不符合6n±1的形式3 6*03。一个健壮的实现必须在优化之前先把这些“特殊情况”处理好。4.3 浮点数陷阱这是一个经典的坑。很多人会想用sqrt函数来获取上界for (int i 2; i sqrt(x); i) // 不推荐为什么不推荐精度问题sqrt返回的是浮点数。浮点数计算和比较可能存在微小的精度误差。例如理论上sqrt(25)等于5但浮点运算结果可能是4.999999999999999导致i sqrt(x)在i5时可能不成立从而漏判。性能问题在循环条件中调用sqrt函数每次循环都会计算一次平方根除非编译器做了优化这比简单的整数除法x / i开销要大。类型转换需要将int转为double计算再转回整型比较增加了不必要的开销。因此始终坚持使用i x / i作为循环条件是C/C中实现试除法的金科玉律。4.4 一个完整的、鲁棒的实现模板结合以上所有讨论这里给出一个我个人在竞赛和工程中都验证过无数次的“终极”试除法模板。它采用了“跳过偶数”的优化在简洁和效率之间取得了很好的平衡。#include iostream using namespace std; bool is_prime(int x) { // 处理所有特殊情况 if (x 2) return false; // 单独处理2和所有偶数 if (x 2) return true; if (x % 2 0) return false; // 只检查奇数因子 for (int i 3; i x / i; i 2) { if (x % i 0) return false; } return true; } int main() { int n; cin n; while (n--) { int x; cin x; if (is_prime(x)) puts(Yes); else puts(No); } return 0; }这个模板的优点正确性妥善处理了所有边界情况负数、0、1、2。高效性通过跳过偶数循环次数减半。安全性使用i x / i避免溢出。清晰性逻辑层次分明易于理解和维护。5. 从模板题到实际应用试除法的局限与超越我们通过AcWing866这道模板题把试除法里里外外剖析了一遍。但作为开发者我们必须清醒地认识到试除法的局限性并知道在什么情况下该寻求更高级的算法。试除法的局限性时间复杂度高O(sqrt(n))。对于单个接近10^18的long long型大整数sqrt(10^18) 10^9这个计算量在现代计算机上也需要数秒时间完全不可接受。仅适用于单点、少量查询如果需要对一个范围内的所有数进行质数判断或者需要频繁查询试除法效率太低。超越试除法更高效的质数判定算法当问题规模超出试除法的能力范围时我们需要更强大的工具Miller-Rabin 素性测试这是一种基于概率的算法。它不能100%确定一个数是质数但可以在极短的时间内以极高的概率通常远高于硬件出错概率给出正确判断。它是目前判断大整数几百位甚至上千位是否为质数的实际标准算法广泛应用于密码学如RSA密钥生成。它的时间复杂度是O(k * log^3 n)其中k是测试轮数通常取10-20轮就足够了。埃拉托斯特尼筛法埃氏筛适用于需要获取一个区间如[1, 10^6]内所有质数的场景。其核心思想是“标记合数”时间复杂度约为O(n log log n)效率远高于对区间内每个数单独试除。线性筛欧拉筛埃氏筛的优化版保证每个合数只被其最小质因子标记一次时间复杂度严格为O(n)。是解决区间质数筛选问题的最优算法。如何选择判断单个、范围不大的数使用优化后的试除法本文模板足矣。判断单个、非常大的数10^12使用 Miller-Rabin 算法。需要得到一段区间内所有质数使用埃氏筛或线性筛。回到我们的AcWing866题它正是“判断单个、范围不大int范围内”的典型场景因此优化试除法是最合适、最直接的工具。掌握它不仅是解决了一道题更是掌握了质数问题最基础的思维模型和代码实现技巧为学习更复杂的算法打下了坚实的基础。下次当你再看到质数判断时希望你能立刻想起i x / i这个巧妙的循环条件以及背后关于效率与正确性的权衡。