1. 项目缘起为什么我们需要“因数质数模板”在编程竞赛、算法面试或者日常的数学计算中处理与质数和因数相关的问题几乎是家常便饭。从判断一个数是否为质数到分解一个数的所有质因数再到生成一定范围内的所有质数这些操作构成了算法基础中不可或缺的一部分。然而很多朋友包括曾经的我在面对这类问题时常常会陷入一些看似简单却暗藏玄机的“坑”里。比如用最朴素的试除法判断大数时超时比如对“1”这个特殊数字的处理不当导致程序崩溃再比如需要快速获取大量质数时写出来的筛法效率低下或者内存爆炸。正是这些反复踩坑、调试、优化的经历让我意识到拥有一套经过实战检验、高效且鲁棒的“因数质数模板”是多么重要。这不仅仅是几行可以复制粘贴的代码更是一套凝结了对于数论基础操作深刻理解的解决方案。它应该像工具箱里的瑞士军刀在面对“判断质数”、“分解质因数”、“线性筛质数”、“求所有因数”等常见需求时能让你信手拈来快速且正确地解决问题从而将宝贵的精力集中在更复杂的逻辑构建上。网络上相关的代码片段很多但往往良莠不齐有的忽略了边界条件有的效率不佳有的缺乏清晰的注释。本项目旨在整理、优化并解释一套完整的、从入门到精通的因数与质数处理模板。我们将从最基础的试除法开始逐步深入到更高效的筛法并探讨其原理、应用场景以及那些容易出错的细节。无论你是正在准备竞赛的学生还是需要应对技术面试的求职者亦或是工作中偶尔需要处理相关问题的开发者相信这份“合集”都能为你提供切实的帮助。2. 质数判定从试除法到Miller-Rabin判断一个正整数n是否为质数是所有相关问题的起点。最直观的方法就是试除法。2.1 基础试除法及其优化试除法的核心思想是一个合数n必定有一个不大于sqrt(n)的质因子。因此我们只需要用2到sqrt(n)之间的所有整数去试除n即可。基础版本def is_prime_naive(n: int) - bool: if n 2: return False for i in range(2, int(n**0.5) 1): if n % i 0: return False return True这个版本对于小的n没问题但效率不高。我们可以立即进行两项关键优化跳过偶数除了2以外所有偶数都不是质数。我们可以先处理2然后只测试奇数。试除到平方根这是数学原理必须遵守。但注意sqrt(n)的计算和循环边界int(n**0.5) 1要小心处理确保边界正确。优化版本def is_prime_trial_division(n: int) - bool: if n 2: return False if n 2: return True if n % 2 0: return False # 只检查奇数因子步长为2 for i in range(3, int(n**0.5) 1, 2): if n % i 0: return False return True注意这里有一个常见的“坑”。range的结束值是不包含的所以必须是int(n**0.5) 1。例如n9sqrt(9)3int(3)14range(3, 4, 2)会包含3从而正确判断9为合数。如果写成range(3, int(n**0.5), 2)当n9时循环不会执行导致错误地将9判断为质数。复杂度分析时间复杂度为 O(√n)。对于n在10^12左右sqrt(n)约为10^6在普通计算机上勉强可接受百万次循环但再大就力不从心了。2.2 应对更大整数的Miller-Rabin素性测试当n非常大比如超过10^12时试除法就太慢了。这时我们需要概率性素性测试算法其中最经典的就是Miller-Rabin测试。它是一个多项式时间算法对于任意奇数n可以以极高的概率判断其是否为质数。通过选择多个不同的“底数”进行测试可以将错误概率降到极低例如使用前12个质数作为底数对于2^64以内的数可以给出确定性判断。算法原理简述 基于费马小定理的推广。如果n是奇质数则将n-1分解为d * 2^s其中d是奇数。对于任意与n互质的整数a以下两个条件之一必然成立a^d ≡ 1 (mod n)存在某个r(0 ≤ r s)使得a^(d * 2^r) ≡ -1 (mod n)如果对于某个底数a以上条件都不成立则n一定是合数。如果成立则n可能是质数。多选几个底数a测试如果都通过则n极大概率是质数。Python实现适用于2^64以内确定性判断def is_prime_miller_rabin(n: int) - bool: if n 2: return False # 处理小质数 small_primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] if n in small_primes: return True for p in small_primes: if n % p 0: return False # 将 n-1 写成 d * 2^s 的形式 d n - 1 s 0 while d % 2 0: d // 2 s 1 # 用前12个质数作为底数进行测试对于 2^64 的数足够 for a in small_primes: if a n: continue x pow(a, d, n) # 快速模幂计算 a^d mod n if x 1 or x n - 1: # 对应条件1或条件2中r0的情况 continue for _ in range(s - 1): x (x * x) % n if x n - 1: # 对应条件2中r0的情况 break else: # 循环正常结束没有break说明两个条件都不满足 return False return True使用心得效率对于大数pow(a, d, n)使用内置的快速模幂运算速度极快复杂度约为 O(k log³ n)其中k是测试轮数。确定性对于n 2^64使用特定的这组小质数底数Miller-Rabin 测试是确定性的即结果100%正确。对于更大的数它仍然是概率性的但错误概率可以忽略不计。应用场景在算法竞赛中如果遇到n极大如10^18的质数判断题Miller-Rabin 是标准解法。在工程中如密码学相关应用也普遍使用它。3. 质因数分解拆解数字的DNA质因数分解是另一个核心操作。给定一个整数n我们想要得到形如{p1: a1, p2: a2, ...}的结果表示n p1^a1 * p2^a2 * ...。3.1 试除法分解最直接的方法依然是试除法在试除过程中计数。def prime_factorization_trial(n: int) - dict: factors {} # 处理因子2 while n % 2 0: factors[2] factors.get(2, 0) 1 n // 2 # 处理奇数因子 i 3 while i * i n: while n % i 0: factors[i] factors.get(i, 0) 1 n // i i 2 # 如果最后剩下的n是大于1的质数 if n 1: factors[n] factors.get(n, 0) 1 return factors示例prime_factorization_trial(360)返回{2: 3, 3: 2, 5: 1}因为360 2^3 * 3^2 * 5。关键点单独处理2这是为了后续循环步长可以为2只检查奇数提升效率。循环条件i * i n这是一个非常重要的优化。在每次整除操作n // i后n会变小。我们只需要试除到sqrt(当前n)即可。因为如果剩下的n是合数它必然有一个不大于其平方根的质因子如果剩下的n是大于1的质数那么它本身就是最后一个质因子。最后的n 1判断如果循环结束后n大于1那么此时的n一定是原始数的一个质因子且是最大的那个。例如分解22处理完2后n11i33*3 11循环结束此时n111所以11是质因子。3.2 结合质数筛的优化分解当需要对一个数进行多次分解或者需要分解的数很大时我们可以先用筛法预处理出一个范围内的质数然后用这些质数去试除避免对合数进行无意义的取模运算。假设我们已经用欧拉筛得到了max_n以内的所有质数列表primes。def prime_factorization_with_sieve(n: int, primes: list) - dict: factors {} for p in primes: if p * p n: # 优化质因子的平方大于当前n时剩余部分必为质数 break while n % p 0: factors[p] factors.get(p, 0) 1 n // p if n 1: factors[n] factors.get(n, 0) 1 return factors这种方法比原始的试除法更快尤其是当n的质因子很多都很小的时候。预处理筛法的成本是 O(max_n)但之后每次分解的成本只与n的质因子个数相关这个个数通常非常少对于一个10^12的数质因子个数最多也就几十个。踩坑记录在分解函数中循环条件用p * p n而不是p n至关重要。前者是 O(√n) 的复杂度后者在最坏情况下n是质数是 O(n) 的复杂度天壤之别。务必记得处理最后n 1的情况否则会漏掉最大的那个质因子。4. 质数筛法批量生产的艺术当需要获取从1到N的所有质数时逐个判断的效率太低。筛法Sieve是解决这类问题的利器。4.1 埃拉托斯特尼筛法埃氏筛这是最古老、最著名的筛法。其原理是从2开始将每个质数的所有倍数标记为合数。def sieve_of_eratosthenes(n: int): is_prime [True] * (n 1) is_prime[0] is_prime[1] False for i in range(2, int(n**0.5) 1): if is_prime[i]: # 从 i*i 开始标记因为 2*i, 3*i, ..., (i-1)*i 已经被更小的质数标记过了 for j in range(i * i, n 1, i): is_prime[j] False primes [i for i, flag in enumerate(is_prime) if flag] return primes复杂度与优化时间复杂度约为 O(n log log n)。已经比 O(n √n) 的逐个判断好太多了。优化点内层循环从i * i开始。这是一个重要的优化。为什么考虑质数5它的倍数5*210已经在质数2时被标记了5*315在质数3时被标记了5*420在质数2时又被标记了。所以第一个需要标记的新合数是5*525。内存优化可以用bytearray或bitset在Python中可用bitarray库来存储布尔数组大幅减少内存占用尤其是当N很大时如10^8。埃氏筛的缺点 同一个合数可能会被多个质数标记多次。例如30 2*15 3*10 5*6它会被质数2、3、5各标记一次。虽然不影响正确性但存在重复操作。4.2 欧拉筛线性筛欧拉筛的核心思想是让每个合数只被其最小的质因子标记一次从而达到理论上的 O(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 # 关键步骤保证每个合数只被最小质因子标记 if i % p 0: break return primes原理解析 这是算法的精髓所在需要仔细理解。外层循环i从2遍历到n。i在这里扮演了两个角色一是它本身可能是质数二是它与已知质数列表primes相乘来生成合数。如果is_prime[i]为真则i是质数加入primes列表。内层循环遍历当前所有的质数p。标记合数i * p为假。关键判断if i % p 0: break当i能被当前质数p整除时即i p * k。那么对于下一个质数p_next要标记的合数是i * p_next (p * k) * p_next p * (k * p_next)。这个合数p * (k * p_next)的最小质因子是p它应该在未来当i k * p_next时用质数p来标记因为i * p (k * p_next) * p等于我们要标记的数。如果此时不break继续用更大的质数p_next去标记i * p_next就相当于让一个合数被一个非最小质因子标记了违背了“只被最小质因子标记”的原则。同时也会导致后续的重复标记。因此一旦发现i % p 0就立即跳出内层循环。举例说明 假设i 4已知质数primes [2, 3]。内层循环p 2标记4*28。判断4 % 2 0break。如果不break继续p 3会标记4*312。但12的最小质因子是2它应该在i6 (6*212)时被标记。现在用3标记了12就重复了而且不是用最小质因子标记的。线性筛的优势真正的 O(n) 时间复杂度每个合数只被标记一次。可以同时得到每个数的最小质因子在标记is_prime[i * p] False时我们可以记录min_prime_factor[i * p] p。这个信息在后续的质因数分解中极其有用可以实现近乎 O(log n) 的分解速度。线性筛的“最小质因子”记录版def linear_sieve_with_lpf(n: int): lpf [0] * (n 1) # lpf[i] 记录数 i 的最小质因子0和1为0 primes [] for i in range(2, n 1): if lpf[i] 0: # i是质数 lpf[i] i primes.append(i) for p in primes: if p lpf[i] or i * p n: # 关键p 不能大于 i 的最小质因子 break lpf[i * p] p return primes, lpf这个版本中lpf数组记录了每个数的最小质因子。内层循环条件p lpf[i]是另一个等价的表述它保证了每个合数i*p被其最小质因子p标记因为lpf[i]是i的最小质因子如果p lpf[i]那么i*p的最小质因子应该是lpf[i]而不是p。使用建议如果只需要质数列表标准欧拉筛第一个版本足够。如果后续需要频繁进行质因数分解强烈推荐使用带lpf的版本。有了lpf分解一个数n的代码将变得异常简洁高效def factorize_using_lpf(n: int, lpf: list) - dict: factors {} while n 1: p lpf[n] cnt 0 while n % p 0: n // p cnt 1 factors[p] cnt return factors这个分解算法的时间复杂度取决于n的质因子个数每次循环至少除以一个质因子所以是 O(log n) 级别比试除法快得多。5. 求所有因数与数论函数解决了质数问题我们常常还需要求一个数的所有正因数或者计算一些数论函数如约数个数、约数和等。5.1 枚举所有正因数基于质因数分解的结果我们可以用回溯法生成所有因数。但更简单直接的方法是遍历1到sqrt(n)找到所有因子对。def get_all_divisors(n: int) - list: divisors [] i 1 while i * i n: if n % i 0: divisors.append(i) if i ! n // i: # 避免重复添加平方根 divisors.append(n // i) i 1 divisors.sort() return divisors原理如果i是n的因数那么n // i也一定是n的因数。我们只需要遍历到sqrt(n)就可以找到所有成对的因数。注意当n是完全平方数时sqrt(n)这个因数会被重复添加一次因为i n // i所以需要if i ! n // i的判断。5.2 计算约数个数与约数和这两个是常见的数论函数。设n的质因数分解为n p1^a1 * p2^a2 * ... * pk^ak。约数个数d(n)每个质因子pi的指数可以从0取到ai共ai1种选择。根据乘法原理总约数个数为(a11) * (a21) * ... * (ak1)。约数和σ(n)所有约数的和。考虑每个质因子pi其贡献的因子和为(1 pi pi^2 ... pi^ai)。所有约数的和就是这些贡献的乘积σ(n) Π( (pi^(ai1) - 1) / (pi - 1) )。代码实现def number_of_divisors(prime_factors: dict) - int: 输入质因数分解字典返回约数个数 result 1 for exp in prime_factors.values(): result * (exp 1) return result def sum_of_divisors(prime_factors: dict) - int: 输入质因数分解字典返回约数和 result 1 for prime, exp in prime_factors.items(): # 计算 (prime^(exp1) - 1) / (prime - 1) # 使用等比数列求和公式用快速幂计算分子 numerator pow(prime, exp 1) - 1 denominator prime - 1 result * (numerator // denominator) # 这里一定能整除 return result示例n360分解为{2:3, 3:2, 5:1}。约数个数 (31)*(21)*(11) 4*3*2 24。约数和 ( (2^4-1)/(2-1) ) * ( (3^3-1)/(3-1) ) * ( (5^2-1)/(5-1) ) (15/1) * (26/2) * (24/4) 15 * 13 * 6 1170。实战技巧计算约数和时pow(prime, exp 1)可能非常大需要注意编程语言的整数范围。Python的整数是任意精度的没问题。但在C/Java中可能需要使用模运算或在计算过程中判断溢出。这些函数通常需要先进行质因数分解。如果是在一个题目中需要频繁计算大量数的约数个数或和可以结合线性筛预处理出每个数的最小质因子然后使用动态规划的思想在线性时间内批量计算出来这属于更进阶的用法。6. 模板整合与实战应用指南将上述各个模块整合起来形成一套完整的工具函数并讨论在不同场景下的选用策略。6.1 完整模板代码Python版class PrimeUtils: 质数与因数工具类 staticmethod def is_prime_trial_division(n: int) - bool: 试除法判质数适用于 n 10^12 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 staticmethod def is_prime_miller_rabin(n: int) - bool: Miller-Rabin素性测试适用于 n 2^64 的确定性判断 if n 2: return False small_primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] if n in small_primes: return True for p in small_primes: if n % p 0: return False d n - 1 s 0 while d % 2 0: d // 2 s 1 for a in small_primes: if a n: continue x pow(a, d, n) if x 1 or x n - 1: continue for _ in range(s - 1): x (x * x) % n if x n - 1: break else: return False return True staticmethod def linear_sieve(n: int): 欧拉筛返回 (质数列表, 最小质因子数组) lpf [0] * (n 1) primes [] for i in range(2, n 1): if lpf[i] 0: lpf[i] i primes.append(i) for p in primes: if p lpf[i] or i * p n: break lpf[i * p] p return primes, lpf staticmethod def prime_factorization_using_lpf(n: int, lpf: list) - dict: 利用最小质因子数组快速质因数分解 factors {} while n 1: p lpf[n] cnt 0 while n % p 0: n // p cnt 1 factors[p] cnt return factors staticmethod def prime_factorization_trial(n: int) - dict: 试除法质因数分解无需预处理 factors {} while n % 2 0: factors[2] factors.get(2, 0) 1 n // 2 i 3 while i * i n: while n % i 0: factors[i] factors.get(i, 0) 1 n // i i 2 if n 1: factors[n] factors.get(n, 0) 1 return factors staticmethod def get_all_divisors(n: int) - list: 获取n的所有正因数已排序 divisors [] i 1 while i * i n: if n % i 0: divisors.append(i) if i ! n // i: divisors.append(n // i) i 1 divisors.sort() return divisors staticmethod def number_of_divisors(prime_factors: dict) - int: 根据质因数分解字典计算约数个数 result 1 for exp in prime_factors.values(): result * (exp 1) return result staticmethod def sum_of_divisors(prime_factors: dict) - int: 根据质因数分解字典计算约数和 result 1 for prime, exp in prime_factors.items(): # 计算 (p^(e1)-1)/(p-1) result * (pow(prime, exp 1) - 1) // (prime - 1) return result6.2 场景化选用指南在实际问题中如何选择这些工具单次判断一个大数是否为质数n可能接近10^18首选is_prime_miller_rabin(n)。这是标准做法速度快结果可靠对于2^64以内确定以上概率极低。需要得到[1, N]范围内的所有质数N 10^7linear_sieve(N)。线性筛是首选O(n)复杂度还可以得到最小质因子数组为后续分解提供便利。N 非常大如 10^8且内存紧张可以考虑用bitset实现埃氏筛或者分段筛。但竞赛和面试中10^7的线性筛基本够用。需要对一个数n进行质因数分解如果已经用线性筛预处理了sqrt(n)或n的范围使用prime_factorization_using_lpf(n, lpf)。这是最快的接近 O(log n)。如果没有预处理且n 10^12使用prime_factorization_trial(n)。试除法足够。如果n非常大如10^18且需要分解这属于“大数分解”问题试除法和筛法都无效。需要更复杂的算法如 Pollards Rho这超出了基础模板的范围通常不会在普通竞赛或面试中出现。需要求一个数的所有因数直接使用get_all_divisors(n)。注意如果n很大如10^12因数的个数可能非常多最多可达几千个输出列表可能会很大。需要计算约数个数或约数和先进行质因数分解得到字典factors然后调用number_of_divisors(factors)或sum_of_divisors(factors)。6.3 常见“坑点”与调试技巧边界条件永远记得处理n 2的情况。1不是质数也不是合数0和负数通常不在讨论范围。循环边界试除法和因数枚举中while i * i n是黄金准则。写成i sqrt(n)或i n**0.5要注意浮点数精度问题最好用乘法比较。重复添加在get_all_divisors中对于完全平方数要避免平方根被添加两次。Miller-Rabin 的底数如果n很大超过2^64使用前12个质数作为底数可能不够需要增加测试轮数或使用随机底数。但在绝大多数场景下这个列表足够了。线性筛的内层循环条件务必理解if i % p 0: break或if p lpf[i]: break的含义这是保证线性的关键。写错会导致错误或超时。性能与内存埃氏筛标记合数时j从i*i开始。线性筛的primes列表和lpf数组大小是n1当n很大时如10^7内存占用约80MBPython列表需要注意。最后再分享一个我个人的调试习惯对于质数相关的函数总是用一些已知的案例进行测试比如2最小质数、3小质数、4最小合数、1边界、0边界、一个大质数如 9999999967、一个大的完全平方数如 1000000000000。观察输出是否符合数学定义是确保代码正确性的最直接方法。把这些模板理解透彻、运用熟练它们将成为你解决数论相关问题最可靠的武器。