1. 项目概述从质数与约数开始打好算法竞赛的数学基石在算法竞赛和日常编程中数学知识从来都不是可有可无的点缀而是决定你能否高效、优雅解决问题的核心内功。很多朋友一看到“数学”两个字就头疼觉得抽象又枯燥但我想说算法中的数学尤其是基础数论部分其实非常“实在”。它不像高数那样有复杂的证明体系更像是一套精巧的工具箱里面装满了像螺丝刀、扳手一样趁手的工具。今天我们就来打开这个工具箱的第一层好好聊聊质数和约数。为什么先从它们开始因为这是整个数论大厦最底下的两块砖。无论是判断一个数能否被整除约数还是寻找最基本的、不可再分的“数字原子”质数亦或是后续会遇到的模运算、最大公约数、同余方程几乎都绕不开这两个概念。我见过太多人在遇到需要分解质因数、求最大公约数GCD的问题时因为基础不牢要么写出的代码效率低下导致超时要么逻辑混乱漏洞百出。掌握它们不仅能让你轻松解决一大类直接相关的题目比如判断质数、分解质因数、求约数个数和更是为你理解更高级的算法如RSA加密基础、欧拉函数、快速幂取模铺平道路。简单来说这部分内容的目标是让你面对一个与质数或约数相关的问题时能立刻在脑海中浮现出几种不同的解法并清楚地知道在数据范围不同的情况下比如数字n是10^6还是10^12该选用哪一种方法才能既保证正确又不超时。我们会从最朴素的思路讲起一步步优化并理解每个优化背后的数学原理。准备好了吗我们开始。2. 质数数字世界的“原子”质数的定义很简单在大于1的自然数中除了1和它本身以外不再有其他因数的数。比如235711。2是唯一的偶质数这个特性在解题时经常被用作优化点。2.1 质数判断从朴素到高效判断一个正整数n是否是质数是最基本的问题。最直接的想法就是试除法。2.1.1 朴素试除法及其问题最朴素的实现是遍历从2到n-1的所有整数看是否能整除n。如果能则不是质数。def is_prime_naive(n): if n 2: return False for i in range(2, n): # 从2遍历到n-1 if n % i 0: return False return True这个方法的时间复杂度是O(n)当n很大时比如10^9完全不可接受。这是新手最容易写出的版本也是第一个需要优化的地方。2.1.2 关键优化一遍历到 sqrt(n) 即可这里涉及一个非常重要的数学原理如果n是一个合数那么它必定有一个不大于√n的质因数。 为什么假设n a * b且a ≤ b。那么a * a ≤ a * b n所以a ≤ √n。也就是说我们只需要检查到√n就够了。如果到√n都没有找到因数那么大于√n的部分更不可能有否则与a≤b矛盾。 这是一个巨大的优化将复杂度从O(n)降到了O(√n)。import math def is_prime_sqrt(n): if n 2: return False # 注意边界range是右开区间所以要1 for i in range(2, int(math.sqrt(n)) 1): if n % i 0: return False return True注意在循环条件中使用i * i n比i sqrt(n)通常更快因为避免了重复计算开方。但要注意i*i可能溢出在Python大整数中没问题在C/Java中对于大n需要注意。写成for i in range(2, int(n**0.5)1):是Python中清晰的写法。2.1.3 关键优化二跳过偶数除了2以外所有偶数都不是质数。因此在判断大于2的奇数时我们可以先排除偶数然后在循环中只检查奇数因子。这能将循环次数减少大约一半。def is_prime_optimized(n): if n 2: return False if n 2: return True if n % 2 0: # 排除所有偶数 return False # 从3开始步长为2只检查奇数 for i in range(3, int(n**0.5) 1, 2): if n % i 0: return False return True对于单个数的判断优化到O(√n)且跳过偶数在算法竞赛中通常已经足够。但在需要频繁判断多个数或者需要获取一个区间内所有质数时我们需要更高效的算法。2.2 质数筛法批量生产的艺术当题目要求找出从1到N之间的所有质数时如果对每个数都用上面的is_prime函数判断总时间复杂度是O(N√N)对于N10^6就已经很吃力了。这时筛法Sieve是唯一的选择。它的核心思想是“标记”而不是“判断”。2.2.1 埃拉托斯特尼筛法埃氏筛这是最经典、最直观的筛法。假设所有数都是质数。从2开始如果当前数是质数则将其所有的倍数从2倍开始标记为合数。继续下一个未被标记的数重复步骤2直到遍历完√N。def sieve_of_eratosthenes(n): is_prime [True] * (n 1) # 初始化所有数为质数 is_prime[0] is_prime[1] False # 0和1不是质数 for i in range(2, int(n**0.5) 1): if is_prime[i]: # 如果i是质数 # 从i*i开始标记因为比i小的倍数已经被之前的质数标记过了 for j in range(i * i, n 1, i): is_prime[j] False # 收集所有质数 primes [i for i in range(2, n1) if is_prime[i]] return primes时间复杂度经过数学分析埃氏筛的时间复杂度约为O(N log log N)已经非常高效。关键细节内层循环从i*i开始。为什么因为对于质数i它的2倍、3倍、…、(i-1)倍一定已经被比i小的质数比如23…标记过了。例如i5时5210被2标记5315被3标记5420被2标记所以从5525开始标记即可。这个优化能减少大量重复操作。2.2.2 线性筛法欧拉筛埃氏筛已经很快但它依然有缺陷一个合数可能会被多个质数重复标记。比如30会被质数2、3、5各标记一次。线性筛的目标是让每个合数只被标记一次从而达到严格的O(N)时间复杂度。其核心思想是让每个合数只被其最小的质因数筛掉。def linear_sieve(n): is_prime [True] * (n 1) primes [] # 用于存放找到的质数 for i in range(2, n 1): if is_prime[i]: primes.append(i) # i是质数加入列表 # 遍历当前已知的所有质数 for p in primes: if i * p n: # 超过范围中断 break is_prime[i * p] False # 用最小质因数p筛掉 i*p if i % p 0: # **关键步骤**保证每个合数只被最小质因数筛一次 break return primes原理剖析if i % p 0: break是线性筛的灵魂。当i % p 0时说明p是i的最小质因数因为primes是从小到大遍历的。那么对于下一个质数p_next要筛的数i * p_next的最小质因数应该是p而不是p_next。如果继续用p_next去筛就会导致i * p_next这个数被重复标记未来当i增长到(i // p) * p_next时又会被p筛一次。因此此时必须break。如何选择在绝大多数算法竞赛场景下N≤10^7时使用经过i*i优化的埃氏筛就足够了代码更简单不易写错。只有当N非常大比如10^8或者后续需要用到质因数分解等需要最小质因数信息的场景时才考虑使用线性筛。线性筛的另一个优势是它可以顺带求出每个数的最小质因数这在分解质因数时非常有用。2.3 质因数分解拆解数字的DNA质因数分解是将一个合数分解为若干个质数相乘的形式如 60 2^2 * 3 * 5。这是解决许多数论问题的关键步骤。2.3.1 试除法分解最直接的方法是用试除法从小到大尝试质因数。def prime_factors(n): factors [] i 2 # 先处理所有因子2 while n % 2 0: factors.append(2) n // 2 # 处理奇数因子从3开始步长为2 i 3 while i * i n: while n % i 0: factors.append(i) n // i i 2 # 如果最后剩下的n大于1它本身就是一个质数 if n 1: factors.append(n) return factors这个算法的时间复杂度也是O(√n)。优化点先单独处理2然后只遍历奇数原理同质数判断。2.3.2 结合筛法预处理的优化如果需要多次进行质因数分解我们可以先用线性筛法预处理出一定范围内比如10^6所有数的最小质因数min_prime_factor。这样分解任何一个数n时我们可以不断地除以它的最小质因数直到n变成1分解过程是O(log n)的。# 预处理部分线性筛变体 def get_min_prime_factors(limit): mpf list(range(limit 1)) # 初始假设每个数的最小质因数是它自己 primes [] for i in range(2, limit 1): if mpf[i] i: # i是质数 primes.append(i) for p in primes: if p mpf[i] or i * p limit: break mpf[i * p] p return mpf # 分解函数 def factorize_with_mpf(n, mpf): factors [] while n 1: p mpf[n] cnt 0 while n % p 0: n // p cnt 1 factors.append((p, cnt)) # 记录质因数p和它的指数cnt return factors这种方法在需要频繁分解质因数的题目中如求多个数的GCD、LCM或者计算约数个数能带来巨大的效率提升。3. 约数理解整除关系约数又称因数是指能整除给定正整数的数。例如12的约数有1, 2, 3, 4, 6, 12。3.1 求一个数的所有约数最直观的方法是遍历1到n判断是否能整除。但和判断质数一样我们可以优化到O(√n)。3.1.1 成对枚举法约数总是成对出现的如果d是n的约数那么n/d也一定是n的约数。我们只需要枚举到 √n 即可。def get_divisors(n): divisors [] i 1 while i * i n: # 枚举到 sqrt(n) if n % i 0: divisors.append(i) if i ! n // i: # 避免重复添加平方根 divisors.append(n // i) i 1 divisors.sort() # 如果需要有序的约数列表 return divisors例如对于n12循环过程i1: 12%10, 加入1和12。i2: 12%20, 加入2和6。i3: 12%30, 加入3和4。i4: 4*412循环结束。 最后排序得到 [1, 2, 3, 4, 6, 12]。3.1.2 通过质因数分解求所有约数有时我们不仅需要约数列表还需要知道约数的个数、总和或者需要生成所有约数进行组合。这时通过质因数分解来构造约数是更强大的方法。 假设n p1^a1 * p2^a2 * ... * pk^ak其中pi是质因数ai是指数。约数个数公式(a11) * (a21) * ... * (ak1)原理每个质因数pi都可以选择0次、1次、...、ai次共(ai1)种选择所有选择相乘即为总的约数个数。约数总和公式(1p1p1^2...p1^a1) * (1p2p2^2...p2^a2) * ... * (1pkpk^2...pk^ak)原理将乘积展开每一项正好对应一个约数。我们可以利用深度优先搜索DFS来生成所有约数def generate_divisors_from_factors(prime_factors): prime_factors: [(p1, a1), (p2, a2), ...] divisors [1] for p, exp in prime_factors: current_len len(divisors) multiplier 1 for _ in range(exp): multiplier * p for i in range(current_len): divisors.append(divisors[i] * multiplier) divisors.sort() return divisors这个方法在约数数量非常多时比如反质数问题比成对枚举更可控。3.2 最大公约数与欧几里得算法最大公约数Greatest Common Divisor, GCD是指两个或多个整数共有约数中最大的一个。最小公倍数Least Common Multiple, LCM则是能够被这两个数整除的最小正整数。它们的关系是lcm(a, b) a * b / gcd(a, b)。3.2.1 辗转相除法欧几里得算法这是计算GCD最著名、最高效的算法。其原理基于一个核心等式gcd(a, b) gcd(b, a % b)。def gcd_euclidean(a, b): while b ! 0: a, b b, a % b return a # 当b为0时a即为最大公约数递归写法更简洁def gcd(a, b): return a if b 0 else gcd(b, a % b)时间复杂度O(log min(a, b))非常快。例如求gcd(1071, 462)gcd(1071, 462) gcd(462, 1071 % 462 147) gcd(147, 462 % 147 21) gcd(21, 147 % 21 0) 213.2.2 更相减损术与优化中国古代的《九章算术》记载了“更相减损术”gcd(a, b) gcd(a-b, b) (ab)。虽然原理正确但当两数相差很大时如gcd(100000000, 1)效率会退化为O(n)。通常不直接使用但它是理解二进制GCD算法的基础。3.2.3 内置函数与LCM计算Python的math模块提供了现成的gcd函数Python 3.5并且从Python 3.9开始提供了lcm函数。import math g math.gcd(12, 18) # 6 l math.lcm(12, 18) # 36 (Python 3.9)如果环境不支持lcm记住公式自己算lcm(a, b) a // math.gcd(a, b) * b。注意先做除法再乘法防止中间结果溢出。3.3 约数相关的常见问题与技巧3.3.1 求多个数的GCD或LCM求多个数的GCD或LCM可以两两合并。def multi_gcd(numbers): result numbers[0] for num in numbers[1:]: result math.gcd(result, num) return result def multi_lcm(numbers): result numbers[0] for num in numbers[1:]: result result // math.gcd(result, num) * num return result3.3.2 判断两个数是否互质如果两个数的最大公约数是1则它们互质。math.gcd(a, b) 1。3.3.3 求一个数的所有约数之和利用前面提到的约数总和公式。在分解质因数后计算def sum_of_divisors(prime_factors): prime_factors: [(p1, a1), (p2, a2), ...] total 1 for p, a in prime_factors: total * (p**(a1) - 1) // (p - 1) # 等比数列求和公式 return total4. 实战应用与综合例题分析理解了概念和算法最终要落到解题上。我们来看几个经典问题把知识串起来。4.1 例题一判断质数AcWing 866. 试除法判定质数问题给定n个正整数ai判定每个数是否是质数。分析典型的单点质数判断。数据范围ai ≤ 2^31-1即约21亿。O(√n)的试除法完全足够。注意使用i*i n的循环条件和跳过偶数的优化。def is_prime(n): if n 2: return False if n 2: return True if n % 2 0: return False i 3 while i * i n: if n % i 0: return False i 2 return True # 对每个输入的ai调用此函数即可4.2 例题二分解质因数AcWing 867. 分解质因数问题给定n个正整数ai将每个数分解质因数并按底数从小到大输出。分析直接使用试除法分解。注意输出格式要求以及如何高效地计算每个质因数的指数。def factorize(n): factors [] i 2 while i * i n: if n % i 0: cnt 0 while n % i 0: n // i cnt 1 factors.append((i, cnt)) i 1 if i 2 else 2 # 巧妙地实现2之后步长为2 if n 1: # 剩下的n是大于sqrt(原n)的质因数 factors.append((n, 1)) return factors关键技巧循环中的i 1 if i 2 else 2是一个简洁的写法实现了先处理因子2之后只遍历奇数。4.3 例题三筛质数AcWing 868. 筛质数问题给定一个正整数n请你求出1~n中质数的个数。n ≤ 10^6。分析筛法模板题。数据范围10^6埃氏筛和线性筛都可以轻松通过。这里给出埃氏筛的实现。def count_primes(n): is_prime [True] * (n 1) count 0 for i in range(2, n 1): if is_prime[i]: count 1 if i * i n: # 防止i*i溢出 for j in range(i * i, n 1, i): is_prime[j] False return count注意内层循环的起始条件j i * i是标准优化。如果担心i*i溢出在C等语言中可以改为j i i或j i * 2但效率稍低。4.4 例题四约数个数与约数之和AcWing 870. 约数个数 871. 约数之和这两题是公式的直接应用。给定n个数求它们乘积的约数个数/之和。核心思路分别分解每个数的质因数。将所有质因数的指数累加。例如a1 2^3 * 3^2, a2 2^1 * 5^2那么乘积的质因数分解为 2^(31) * 3^2 * 5^2。利用公式计算。# 以约数个数为例假设已获得所有质因数的总计数 count_dict MOD 10**9 7 def count_divisors(count_dict): res 1 for exp in count_dict.values(): res res * (exp 1) % MOD return res4.5 例题五最大公约数AcWing 872. 最大公约数问题求n对正整数的最大公约数。分析直接调用欧几里得算法即可。这是最没有悬念的一题但却是很多复杂问题的基础组件。5. 常见“坑点”与经验总结在多年的刷题和教学过程中我总结了一些新手容易踩的坑和值得注意的经验。5.1 时间复杂度估算与优化选择这是最重要的思维习惯。看到一个题目首先要根据数据范围选择算法。单个数n判断质数/分解质因数/求约数如果n ≤ 10^12O(√n)的试除法是可行的√10^12 10^6。如果n更大就需要更高级的算法如Miller-Rabin素性测试、Pollard-Rho因数分解。求1~n所有质数如果n ≤ 10^7埃氏筛或线性筛。如果n ≤ 10^5甚至可以用简单的试除法逐个判断总复杂度O(n√n)勉强可过。求一个数的所有约数O(√n)的枚举法在约数数量不多时很好。但如果需要利用约数进行复杂组合或者已知质因数分解用DFS生成可能更清晰。一个经验法则在一般的算法竞赛中如蓝桥杯、ACM校赛O(10^7)的操作量是安全边界。O(10^8)需要常数很小的优化O(10^9)基本不可行。5.2 边界条件与特殊值处理1不是质数也不是合数这是定义但在判断时很容易忽略。if n 2: return False。2是唯一的偶质数在循环优化时先特判2然后从3开始步进2。平方数在枚举约数时如果i*i n那么i和n//i是同一个数只添加一次避免重复。大数乘法溢出在计算i*i或者a*b在求LCM时时在C/Java中要小心溢出必要时使用长整型(long long)。Python大整数自动处理无需担心。模运算在计算约数个数/之和等需要取模的题目时公式中的除法如等比数列求和公式(p^(a1)-1)/(p-1)不能直接取模需要计算逆元。但题目通常保证p-1与模数MOD互质可以用费马小定理求逆元。这是一个进阶知识点但在此类基础题中题目常会说明“答案对10^97取模”并保证计算过程不会出现分数。5.3 代码实现的简洁性与效率循环条件while i * i n比while i sqrt(n)好因为每次循环都重新计算sqrt(n)开销大。但要注意i*i的溢出问题Python无此问题。使用内置函数在Python中math.gcd是C实现的比自己写的递归或循环要快得多。积极使用。列表生成与排序在求约数时成对添加后记得排序如果题目需要有序。divisors.sort()的时间复杂度是O(k log k)其中k是约数个数通常可以接受。筛法的空间优化埃氏筛可以用bytearray或bitset在C中来减少内存占用。线性筛需要存储质数列表和最小质因数数组空间稍大。5.4 从质数与约数到更广阔的数论世界掌握质数和约数是打开了数论的第一扇门。以此为起点你可以继续深入同余与模运算这是密码学和许多算法的核心。欧拉函数计算小于n且与n互质的数的个数在RSA加密中至关重要。扩展欧几里得算法求解线性同余方程ax ≡ 1 (mod m)即求a模m的逆元的关键。中国剩余定理解决一组同余方程组。组合数学中的质因数应用计算组合数C(n, m)时常常需要分解质因数来避免除法取模。质数和约数的知识就像一把万能钥匙基础但强大。我建议在初学阶段不要仅仅满足于AC题目而是要把每个模板代码都敲上几遍理解每一行代码背后的数学原理和优化动机。这样当遇到变种题或者需要将这些知识作为子模块嵌入更复杂的问题时你才能游刃有余。