1. 从“口袋里的质数”说起为什么算法离不开数学最近在网上看到一个挺有意思的题目大意是小A有一个“质数口袋”从2开始依次判断各个自然数如果是质数就装进口袋。这个描述虽然简单却精准地戳中了算法学习中的一个核心痛点——数学知识尤其是数论基础。很多刚开始接触算法的朋友一看到“动态规划”、“图论”就头大殊不知很多看似复杂的算法问题其底层逻辑往往建立在像质数判断、最大公约数计算这样基础的数学概念之上。你可能会用暴力枚举通过一些简单题但一旦数据规模上去或者题目需要一点数学上的“巧劲”立刻就会卡壳。我自己在刷题和面试中深有体会。比如快速判断一个超大整数是否为质数像热词里提到的“99999999977是质数吗”这种问题或者需要高效地求出一段区间内所有数的约数个数如果只懂最基础的从2遍历到n的试除法时间复杂度是O(n)在n很大时根本不可行。这时就需要更高效的数学算法比如埃拉托斯特尼筛法来批量找质数或者用质因数分解结合约数个数公式来快速求解。这些都不是凭空想象出来的技巧而是有严密数学原理支撑的。所以这个“算法基础课—数学知识”系列我想就从最根本的质数和约数讲起。这不仅仅是记忆几个模板代码更重要的是理解背后的数学原理明白“为什么这个算法快”以及“在什么场景下该用哪个算法”。无论是准备编程竞赛还是应对技术面试甚至是从事机器学习、密码学像AES、ECC这些加密算法都深深依赖数论等领域扎实的初等数论基础都是你不可或缺的武器。接下来我们就抛开枯燥的定义直接进入实战看看这些数学知识是如何在代码中“活”起来的。2. 质数不只是“只能被1和自身整除”质数的定义大家都很熟悉在大于1的自然数中除了1和它本身以外不再有其他因数的数。但算法关心的是操作如何判断和如何寻找。2.1 试除法从暴力到优化最直观的方法就是试除法。给定一个数n用2到n-1的每个数去试除如果都不能整除n就是质数。def is_prime_naive(n: int) - bool: if n 2: return False for i in range(2, n): # 从2遍历到n-1 if n % i 0: return False return True这个方法的时间复杂度是O(n)效率极低。想象一下判断“99999999977”这种11位数要循环近千亿次完全不现实。优化一试除到 sqrt(n)关键洞察如果n是一个合数那么它必定有一个不大于其平方根的因子。假设n a * b如果a和b都大于sqrt(n)那么a*b n矛盾。因此我们只需要试除到int(sqrt(n))即可。import math def is_prime_sqrt(n: int) - bool: if n 2: return False # 注意边界i需要取到sqrt(n)。例如n4需要试除到2。 for i in range(2, int(math.isqrt(n)) 1): # math.isqrt是求整数平方根Python 3.8 if n % i 0: return False return True时间复杂度降为O(√n)。对于99999999977只需要试除到约316227循环次数从千亿级降到几十万级虽然对于单次判断大数依然有压力但已经实用很多。优化二跳过偶数除了2以外所有偶数都不是质数。我们可以先处理偶数情况然后在循环中只测试奇数。def is_prime_optimized(n: int) - bool: if n 2: return False if n 2: return True if n % 2 0: # 排除所有偶数 return False # 从3开始步长为2只检查奇数 for i in range(3, int(math.isqrt(n)) 1, 2): if n % i 0: return False return True这样循环次数大约减半。注意math.isqrt()是比int(math.sqrt(n))更安全、更快的选择它直接返回整数平方根避免了浮点数精度问题。2.2 批量生产的艺术筛法当需要找出一定范围内比如1到N的所有质数时使用筛法是绝对的主流。它的核心思想不是“判断”而是“标记排除”。埃拉托斯特尼筛法是最经典的。算法步骤如下假设所有数从2开始初始都是质数。从2开始如果当前数是质数则将其所有的倍数标记为合数。继续下一个未被标记的数重复步骤2直到处理完所有数。def sieve_of_eratosthenes(n: int): 返回一个布尔列表 is_primeis_prime[i] 为 True 表示 i 是质数。 索引从0开始但通常我们只关心 2 的部分。 if n 2: return [False] * (n 1) is_prime [True] * (n 1) is_prime[0] is_prime[1] False # 0和1不是质数 for i in range(2, int(math.isqrt(n)) 1): # 同样只需筛到 sqrt(n) if is_prime[i]: # 如果 i 是质数 # 从 i*i 开始标记因为比 i*i 小的 i 的倍数已经被更小的质数标记过了 # 例如 i5时5*210已被i2标记5*315已被i3标记5*420已被i2标记 for j in range(i * i, n 1, i): is_prime[j] False return is_prime # 示例找出100以内的所有质数 N 100 is_prime sieve_of_eratosthenes(N) primes [i for i in range(2, N1) if is_prime[i]] print(primes) # 输出[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]埃氏筛的时间复杂度是O(n log log n)空间复杂度O(n)。对于N10^6一百万以内的质数筛选它可以在毫秒级完成非常高效。线性筛欧拉筛是埃氏筛的改进版其核心是保证每个合数只被其最小的质因子筛掉一次从而达到严格O(n)的时间复杂度。这对于需要处理极大N比如上亿且对时间极其敏感的场景很有用。实现上稍复杂它需要维护一个质数列表。def linear_sieve(n: int): 线性筛法返回质数列表。 is_prime [True] * (n 1) primes [] # 存放找到的质数 for i in range(2, n 1): if is_prime[i]: primes.append(i) # 遍历当前已知的所有质数 for p in primes: if i * p n: break is_prime[i * p] False # 关键如果 p 是 i 的质因子则跳出循环。 # 这保证了每个合数只被其最小质因子筛一次。 # 例如 i4时质数列表为[2,3]。4*28被筛且2整除4跳出不会用4*312去筛。 # 而12会在 i6时被其最小质因子2筛掉 (6*212)。 if i % p 0: break return primes实操心得在绝大多数算法竞赛和面试场景中埃氏筛已经完全够用且代码更简洁更容易记忆和书写。除非题目数据范围巨大如N10^7且时间卡得非常死否则优先使用埃氏筛。线性筛的理解和实现成本更高可以作为进阶知识掌握。2.3 质因数分解拆解数字的DNA任何一个大于1的整数都可以唯一地分解成若干个质数的乘积。这就是算术基本定理。质因数分解是解决很多约数相关问题的基石。方法很简单从2开始试除如果能整除就记录这个质因子并一直除到不能整除为止然后增加试除的数。def prime_factorization(n: int): 返回一个列表记录n的质因数分解结果如 12 - [2, 2, 3] factors [] i 2 # 先处理因子2可以快速减少n while n % 2 0: factors.append(2) n // 2 # 处理奇数因子从3开始步长为2 i 3 while i * i n: # 只需检查到 sqrt(当前的n) while n % i 0: factors.append(i) n // i i 2 # 如果最后剩下的n大于1它本身就是一个质数 if n 1: factors.append(n) return factors print(prime_factorization(60)) # 输出[2, 2, 3, 5] print(prime_factorization(99999999977)) # 这是一个质数输出[99999999977]通常我们更关心每个质因子的指数。可以用字典来存储def prime_factorization_dict(n: int): factors {} i 2 while i * i n: while n % i 0: factors[i] factors.get(i, 0) 1 n // i i 1 if i 2 else 2 # 第一次后跳过偶数 if n 1: factors[n] factors.get(n, 0) 1 return factors print(prime_factorization_dict(360)) # 输出{2: 3, 3: 2, 5: 1} 即 2^3 * 3^2 * 53. 约数理解整数的“因子关系”约数又称因数是指能整除给定整数的整数。例如6的约数有1, 2, 3, 6。3.1 求一个数的所有约数最直接的方法是遍历1到n但同样有优化空间。和质数判断类似约数也是成对出现的如果d是n的约数那么n/d也是。因此只需要遍历到sqrt(n)。def get_divisors(n: int): 返回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 print(get_divisors(12)) # 可能输出[1, 12, 2, 6, 3, 4]时间复杂度O(√n)。注意结果中约数对是无序的如果需要有序列表记得排序排序复杂度O(d log d)d是约数个数通常很小。3.2 约数个数与约数之和公式的力量如果已经对数字n完成了质因数分解n p1^a1 * p2^a2 * ... * pk^ak那么我们可以直接通过公式计算而无需枚举所有约数。约数个数d(n) (a1 1) * (a2 1) * ... * (ak 1)原理每个质因子pi在约数中的指数可以从0取到ai共ai1种选择。所有选择相乘即为总的约数个数。约数之和σ(n) (p1^(a11)-1)/(p1-1) * (p2^(a21)-1)/(p2-1) * ... * (pk^(ak1)-1)/(pk-1)原理这是等比数列求和公式的乘积。约数之和等于所有(pi^0 pi^1 ... pi^ai)的乘积。def number_of_divisors(prime_factors: dict): 根据质因数分解的字典返回约数个数。 count 1 for exp in prime_factors.values(): count * (exp 1) return count def sum_of_divisors(prime_factors: dict): 根据质因数分解的字典返回约数之和。 total 1 for prime, exp in prime_factors.items(): total * (pow(prime, exp 1) - 1) // (prime - 1) return total # 示例n12 2^2 * 3^1 pf {2: 2, 3: 1} print(number_of_divisors(pf)) # (21)*(11)6 约数有1,2,3,4,6,12 print(sum_of_divisors(pf)) # ((2^3-1)/(2-1)) * ((3^2-1)/(3-1)) 7 * 4 28这两个公式在解决诸如“求1到N中约数个数最多的数”、“求某个数的所有约数之和”等问题时效率远高于枚举。3.3 最大公约数与最小公倍数欧几里得的智慧最大公约数Greatest Common Divisor, GCD和最小公倍数Least Common Multiple, LCM是数论中应用最广泛的概念之一在分数化简、周期相遇、加密算法如RSA中都有出现。辗转相除法欧几里得算法计算GCD的经典算法。基于原理gcd(a, b) gcd(b, a % b)。当余数为0时除数即为最大公约数。def gcd_euclidean(a: int, b: int) - int: while b: a, b b, a % b return abs(a) # 返回绝对值确保正数 print(gcd_euclidean(48, 18)) # 输出6更简洁的递归写法def gcd(a: int, b: int) - int: return a if b 0 else gcd(b, a % b)最小公倍数可以利用GCD快速求得。因为a * b gcd(a, b) * lcm(a, b)。def lcm(a: int, b: int) - int: return abs(a // gcd(a, b) * b) # 先除后乘避免中间结果溢出Python 3.9 的标准库math中已经内置了math.gcd()和math.lcm()函数可以直接使用。踩坑提醒计算LCM时切忌使用a * b // gcd(a, b)虽然数学上等价但在编程中a*b可能会在除法发生前就发生整数溢出尤其是在C/Java等语言中。务必先除后乘a // gcd(a, b) * b。Python的整数不会溢出但养成这个习惯对编写跨语言代码很重要。4. 算法实战当数学知识遇上编程题理解了原理我们来看几个经典问题感受一下如何将数学知识转化为AC代码。4.1 例题一判定质数AcWing 866. 试除法判定质数问题描述给定n个正整数ai判定每个数是否是质数。输入格式第一行整数n接下来n行每行一个ai。数据范围1 ≤ n ≤ 100, 1 ≤ ai ≤ 2^31 - 1注意ai可以很大是32位整数上限。分析这就是最直接的质数判定。对于每个ai使用优化后的试除法试除到sqrt(ai)且跳过偶数。注意边界条件1不是质数2是质数。import sys import math def is_prime(x: int) - bool: if x 2: return False if x 2: return True if x % 2 0: return False i 3 while i math.isqrt(x): if x % i 0: return False i 2 # 只检查奇数 return True def main(): n int(sys.stdin.readline()) for _ in range(n): a int(sys.stdin.readline()) print(Yes if is_prime(a) else No) if __name__ __main__: main()4.2 例题二筛质数AcWing 868. 筛质数问题描述给定一个正整数n请你求出1~n中质数的个数。数据范围1 ≤ n ≤ 10^6。分析典型的筛法应用。n最大为10^6埃氏筛O(n log log n)完全可行代码也简单。直接套用前面的埃氏筛模板最后统计is_prime列表中True的个数。import sys import math def count_primes(n: int) - int: if n 2: return 0 is_prime [True] * (n 1) is_prime[0] is_prime[1] False for i in range(2, int(math.isqrt(n)) 1): if is_prime[i]: # 从i*i开始标记 for j in range(i * i, n 1, i): is_prime[j] False # 统计质数个数 return sum(is_prime) # 或者用 is_prime.count(True) def main(): n int(sys.stdin.readline()) print(count_primes(n)) if __name__ __main__: main()4.3 例题三约数个数AcWing 870. 约数个数问题描述给定n个正整数ai请你输出这些数的乘积的约数个数答案对10^97取模。数据范围1 ≤ n ≤ 100, 1 ≤ ai ≤ 2 * 10^9。分析如果先求所有数的乘积再分解质因数乘积可能巨大无比100个2e9相乘绝对溢出。正确做法是利用约数个数公式。乘积的质因数分解等于每个数质因数分解的指数相加。步骤用一个全局字典factor_cnt记录所有质因子的总指数。对每个数ai进行质因数分解将分解结果中的每个质因子p及其指数exp累加到factor_cnt[p]中。所有数处理完后根据公式d Π (exp_i 1)计算约数个数。import sys from collections import defaultdict MOD 10**9 7 def main(): n int(sys.stdin.readline()) factor_cnt defaultdict(int) # 质因子 - 总指数 for _ in range(n): a int(sys.stdin.readline()) # 对a进行质因数分解 i 2 while i * i a: while a % i 0: factor_cnt[i] 1 a // i i 1 if i 2 else 2 # 优化2之后只检查奇数 if a 1: # 剩下的a是质数 factor_cnt[a] 1 # 计算约数个数 res 1 for exp in factor_cnt.values(): res res * (exp 1) % MOD print(res) if __name__ __main__: main()4.4 例题四最大公约数AcWing 872. 最大公约数问题描述给定n对正整数ai, bi请你求出每对数的最大公约数。数据范围1 ≤ n ≤ 10^5, 1 ≤ ai, bi ≤ 2 * 10^9。分析直接调用欧几里得算法辗转相除法即可。数据范围很大但辗转相除法复杂度是O(log min(a,b))非常快。注意使用内置math.gcd或自己实现。import sys import math def main(): n int(sys.stdin.readline()) for _ in range(n): a, b map(int, sys.stdin.readline().split()) print(math.gcd(a, b)) if __name__ __main__: main()5. 进阶思考与常见陷阱掌握了基础操作我们还需要思考一些边界情况和优化技巧。5.1 质数判断的更多细节大数判断与Miller-Rabin算法对于远超64位的大整数比如几百位的质数在密码学中常见试除法甚至优化后的试除法都太慢。这时需要概率性质数测试算法如Miller-Rabin算法。它是一个多项式时间算法可以极大概率判断一个大数是否为质数。Python的sympy库和gmpy2库中有现成实现。对于算法竞赛一般不会考到需要自己实现Miller-Rabin的程度但要知道有这个东西。1不是质数也不是合数这是一个常见的逻辑错误起点在写判断函数时务必首先处理n 2的情况。循环边界for i in range(2, int(math.sqrt(n)) 1)中的1至关重要因为range是左闭右开区间需要包含sqrt(n)这个边界值。使用math.isqrt(n)则可以直接for i in range(2, isqrt_n 1)。5.2 筛法的性能与内存优化埃氏筛的“从i*i开始”这是一个重要优化。对于质数i比i*i小的i的倍数如i*2,i*3, ...,i*(i-1)一定已经被比i小的质数筛过了。例如i5时5*210已被i2筛掉5*315已被i3筛掉。只筛奇数可以进一步优化埃氏筛先单独处理2然后只考虑奇数。这样数组大小和循环次数都能减半。分段筛法当需要筛选的区间[L, R]非常大比如R在10^12级别但区间长度R-L1相对可接受时无法直接开出R1大小的数组。这时可以使用分段筛先在sqrt(R)范围内筛出质数再用这些质数去筛[L, R]区间内的合数。5.3 约数相关的综合问题求多个数的最大公约数gcd(a, b, c) gcd(gcd(a, b), c)可以迭代计算。求多个数的最小公倍数lcm(a, b, c) lcm(lcm(a, b), c)。注意计算过程中同样要防止溢出。枚举所有约数对在解决问题“找到两个数使其乘积等于给定数N”或“枚举矩形的长宽”时使用for i in range(1, int(sqrt(n))1): if n % i 0: ...的循环是最佳实践复杂度O(√n)。5.4 一个综合案例完美平方数问题问题给定一个整数n判断它是否是一个完美平方数并且它的平方根是否是一个质数。思路拆解首先判断是否为完美平方数。可以用int(math.sqrt(n)) ** 2 n或者math.isqrt(n) ** 2 n。如果是计算其平方根r。然后判断r是否为质数。import math def is_prime_square(n: int) - bool: if n 4: # 最小的质数平方是4 (2^2) return False r math.isqrt(n) if r * r ! n: # 不是完美平方数 return False # 判断r是否为质数 if r 2: return False if r 2: return True if r % 2 0: return False for i in range(3, int(math.isqrt(r)) 1, 2): if r % i 0: return False return True # 测试 print(is_prime_square(4)) # True (2是质数) print(is_prime_square(9)) # True (3是质数) print(is_prime_square(16)) # False (4不是质数) print(is_prime_square(25)) # True (5是质数) print(is_prime_square(49)) # True (7是质数) print(is_prime_square(121)) # False (11是质数但12111^2判断的是11所以是True等等需要仔细看函数名。这个函数判断的是n本身是否是“质数的平方”。121是11的平方11是质数所以应该返回True。实际测试会返回True。这个例子展示了如何将质数判断和平方根判断组合起来解决一个稍复杂的问题。在算法题中这种多步骤的复合条件判断非常常见。质数和约数的知识就像算法世界里的砖石看似简单却是构建复杂逻辑的基石。从基础的判断与枚举到高效的筛法与公式计算再到与GCD/LCM的结合这些内容贯穿了无数算法题目。理解其原理熟练其代码模板并在实战中注意边界和优化就能在面对相关问题时游刃有余。我个人的经验是把这些基础数学算法的模板代码背熟理解透在比赛或面试中就能节省大量思考时间把精力留给更复杂的算法逻辑本身。