1. 项目概述为什么我们需要一个“因数质数模板合集”在编程和算法学习的路上无论你是刚入门的新手还是已经有一定经验的开发者几乎都绕不开“因数”和“质数”这两个老朋友。它们就像是数学世界里的“砖”和“瓦”是构建更复杂逻辑和解决更高级问题的基础。我见过太多朋友在刷题或者做项目时每次遇到判断质数、分解质因数、求最大公约数这类问题都要临时去网上搜一段代码或者重新推导一遍逻辑。这不仅效率低下更重要的是网上代码质量参差不齐有些实现存在性能陷阱比如用最朴素的O(n)方法去判断一个大数是否为质数程序直接卡死。所以我决定整理一份自己十多年来积累和优化过的“因数质数模板合集”。这个合集不是一个简单的代码仓库而是一个经过实战检验的工具箱。它包含了从最基础的判断、生成到应用于复杂场景如质因数分解求欧拉函数、筛法求区间质数的各种高效、可靠的代码实现。无论你是要快速解决一道算法题还是要在自己的项目中集成可靠的数学计算模块这个合集都能让你直接“抄作业”把时间花在更核心的逻辑上而不是反复调试这些基础轮子。2. 核心算法原理与选型考量为什么有的质数判断算法快如闪电有的却慢如蜗牛为什么“筛法”家族如此庞大选择哪种实现背后是时间复杂度、空间复杂度以及具体应用场景的权衡。理解这些“为什么”你才能在任何情况下选出最合适的“工具”。2.1 质数判断从试除法到Miller-Rabin1. 朴素试除法 (Trial Division)这是最直观的方法对于一个正整数n用2到n-1之间的所有整数去试除如果都不能整除则n是质数。时间复杂度O(n)。对于大的n完全不可接受。优化1除数只需要检查到√n。因为如果n有一个大于√n的因子a那么必然有一个小于√n的因子bn a * b。时间复杂度降至 O(√n)。优化2先检查n是否为偶数除了2。然后从3开始每次加2只检查奇数。因为偶数除了2肯定不是质数。这能让循环次数减半。2. 埃拉托斯特尼筛法 (Sieve of Eratosthenes)用于高效生成一定范围内比如[2, n]的所有质数。其核心思想是“标记排除”。假设所有数初始都是质数。从2开始如果它是质数则将其所有倍数标记为非质数。继续找到下一个未被标记的数重复步骤2直到处理完√n以内的数。时间复杂度O(n log log n)接近线性在生成大量质数时效率极高。空间复杂度O(n)需要一个长度为n1的布尔数组。常见优化仅标记奇数除了2所有偶数都不是质数。可以只申请一半的空间处理奇数。从 i*i 开始标记对于质数i其小于i*i的倍数如2*i,3*i, ...一定已经被更小的质数标记过了。可以从i*i开始标记。使用位运算压缩空间用bitset或整数的每一位来表示一个数的状态可以将空间消耗减少到原来的 1/32 或 1/64。3. 线性筛法 (欧拉筛Euler‘s Sieve)埃氏筛的一个问题是一个合数可能会被多个质数重复标记例如12会被2和3各标记一次。线性筛保证了每个合数只被其最小的质因子标记一次从而实现严格的 O(n) 时间复杂度。核心流程维护一个质数列表primes。遍历每个数i用i乘以当前质数列表中的每个质数p将i * p标记为合数。关键在于当i % p 0时立即跳出内层循环。这保证了p是i * p的最小质因子。优势O(n) 时间复杂度且能同时得到每个数的最小质因子这在后续的质因数分解中非常有用。劣势代码比埃氏筛稍复杂且实际运行常数可能比优化后的埃氏筛大。对于单纯生成质数列表埃氏筛通常更常用当需要最小质因子信息时线性筛是首选。4. Miller-Rabin 素性测试这是处理极大整数如超过 10^18质数判断的唯一实用方法。它是一种概率性算法但通过选择多个底数进行测试可以将错误概率降到极低远低于硬件出错概率在实际应用中可视为确定性算法。原理基于费马小定理和二次探测定理。对于一个待测数n随机选择一些底数a进行测试。如果所有测试都通过则n很可能是质数如果任何一次测试失败则n一定是合数。时间复杂度O(k log³ n)其中k是测试轮数。对于 64 位整数选择 7 个特定的底数[2, 325, 9375, 28178, 450775, 9780504, 1795265022]进行测试可以保证 100% 正确。应用场景RSA 密钥生成、大数质数判断竞赛题。选择建议对于日常算法题n ≤ 10^7优化后的试除法到 √n足够快且简单。对于需要生成大量质数n ≤ 10^7用埃氏筛。如果需要知道每个数的最小质因子用于快速质因数分解用线性筛。对于 n 10^14 的大整数必须用 Miller-Rabin。2.2 因数与质因数分解1. 枚举所有因数最直接的方法是遍历1到√n如果i能整除n则i和n/i都是一对因数。注意处理i n/i的情况以避免重复。时间复杂度 O(√n)。2. 质因数分解 (Prime Factorization)将n分解为若干个质数的乘积如60 2² × 3 × 5。这是很多数论问题的基础。方法一试除法。从2开始循环判断n是否能被当前数i整除。如果能则一直除到不能整除为止记录i的指数然后i。同样i只需要循环到√n。时间复杂度 O(√n)。方法二基于线性筛预处理最小质因子。这是更高效的方法尤其适用于需要对多个数进行分解的场景。先用线性筛法预处理出max_n范围内每个数的最小质因子min_prime。分解n时不断n / min_prime[n]并记录这个质因子直到n 1。由于每次除的都是最小质因子分解速度极快时间复杂度约为 O(log n)。3. 模板代码实现与逐行解析理论说再多不如一行代码。下面是我精心打磨的几个核心模板附上详细注释和注意事项。3.1 质数判断模板模板1优化试除法 (适用于 n ≤ 10^12)def is_prime_trial(n: int) - bool: 优化试除法判断质数 if n 2: return False if n 2 or n 3: return True if n % 2 0 or n % 3 0: # 排除偶数除2和3的倍数 return False # 检查6k±1形式的数即5, 7, 11, 13, 17, 19... i 5 step 2 # 初始步长2用于在5和7之间切换 while i * i n: # 只需检查到根号n if n % i 0: return False i step step 6 - step # 步长在2和4之间切换实现 i: 5-7-11-13... return True逐行解析与心得if n % 2 0 or n % 3 0: 在循环开始前快速排除大量合数这是一个非常有效的预处理。i 5; step 2: 核心优化点。所有大于3的质数都可以表示为6k±1的形式。所以我们只需要检查5, 7, 11, 13, 17, 19...。这比逐个检查奇数3,5,7,9...少了三分之一的工作量。step 6 - step: 这是一个巧妙的技巧让step在2和4之间交替。i 2(5-7), 然后step4,i4(7-11), 再step2,i2(11-13)如此循环。模板2埃拉托斯特尼筛法 (生成 [2, n] 内所有质数)def sieve_of_eratosthenes(n: int): 埃拉托斯特尼筛法返回布尔数组 is_primeis_prime[i] 表示 i 是否为质数 if n 2: return [False] * (n 1) is_prime [True] * (n 1) is_prime[0] is_prime[1] False # 0和1不是质数 # 只遍历到根号n for i in range(2, int(n ** 0.5) 1): if is_prime[i]: # 从 i*i 开始标记步长为 i for j in range(i * i, n 1, i): is_prime[j] False return is_prime # 使用示例获取所有质数列表 def get_primes(n): is_prime sieve_of_eratosthenes(n) return [i for i in range(2, n1) if is_prime[i]]注意事项range(i * i, n 1, i): 这里一定要从i*i开始。比如i55*210和5*315肯定已经在i2和i3时被标记过了。从i*i开始能避免大量重复工作。当n很大比如上亿时is_prime列表会占用大量内存。可以考虑使用bytearray或第三方库如bitarray来优化。模板3线性筛法 (同时获取最小质因子)def linear_sieve(n: int): 线性筛欧拉筛返回质数列表 primes 和最小质因子数组 min_prime min_prime [0] * (n 1) # min_prime[i] 记录 i 的最小质因子0表示质数或未处理 primes [] for i in range(2, n 1): if min_prime[i] 0: # i 是质数 min_prime[i] i primes.append(i) # 用当前质数表里的质数 p 去标记合数 i * p for p in primes: if p min_prime[i] or i * p n: break # 关键如果 p 大于 i 的最小质因子或乘积超范围则跳出 min_prime[i * p] p # 标记 i*p 的最小质因子为 p return primes, min_prime核心难点解析if p min_prime[i] or i * p n: break这一行是线性筛的灵魂。p min_prime[i]保证了每个合数只被其最小质因子标记一次。例如i4(min_prime[4]2)质数列表为[2,3]。当p2时标记4*28(min_prime[8]2)。然后p3因为3 min_prime[4] (2)所以跳出循环。这样12就不会在i4时被p3标记而是留到i6(min_prime[6]2) 时用p2来标记。这就确保了唯一性。i * p n简单的越界检查。3.2 质因数分解模板模板4基于线性筛的快速质因数分解def prime_factorization_fast(n: int, min_prime: list) - dict: 快速质因数分解返回字典 {质因子: 指数} 参数 min_prime 来自 linear_sieve 函数预处理的结果 factors {} while n 1: p min_prime[n] # 取出当前 n 的最小质因子 cnt 0 while n % p 0: n // p cnt 1 factors[p] cnt return factors # 使用示例 n 100 max_range 100 # 预处理的范围需要至少为 n _, min_prime linear_sieve(max_range) factors prime_factorization_fast(n, min_prime) print(factors) # 输出: {2: 2, 5: 2} 表示 100 2^2 * 5^2优势分解一个数n的时间复杂度约为 O(log n)速度极快。前提是需要预先用线性筛处理好min_prime数组适用于需要多次分解的场景。模板5不依赖预处理的试除分解法def prime_factorization(n: int) - dict: 试除法质因数分解无需预处理 factors {} # 处理因子2 while n % 2 0: factors[2] factors.get(2, 0) 1 n // 2 # 处理奇数因子从3开始步长为2 i 3 while i * i n: while n % i 0: factors[i] factors.get(i, 0) 1 n // i i 2 # 如果最后剩下的 n 是大于2的质数 if n 1: factors[n] factors.get(n, 0) 1 return factors心得先单独处理2然后从3开始每次加2检查奇数。这是一个非常经典且实用的写法。循环条件是i * i n因为当n被除到小于i²时它要么是1要么是一个质数就是当前剩下的n。3.3 求所有因数、最大公约数与最小公倍数模板6枚举所有正因数def get_factors(n: int) - list: 返回 n 的所有正因数列表无序 if n 0: return [] factors [] i 1 while i * i n: if n % i 0: factors.append(i) if i ! n // i: # 避免重复添加平方根 factors.append(n // i) i 1 # 可以排序后返回但有时无序也能满足需求 # factors.sort() return factors模板7欧几里得算法求最大公约数 (GCD) 和最小公倍数 (LCM)def gcd(a: int, b: int) - int: 递归版欧几里得算法 return a if b 0 else gcd(b, a % b) def gcd_iterative(a: int, b: int) - int: 迭代版欧几里得算法避免递归深度限制 while b: a, b b, a % b return a def lcm(a: int, b: int) - int: 最小公倍数注意先除后乘防止溢出 return a // gcd(a, b) * b重要提示计算lcm时务必使用a // gcd(a, b) * b而不是a * b // gcd(a, b)。虽然数学上等价但在编程中先乘后除可能导致中间结果a*b溢出整数范围而先除后乘则可以避免这个问题。4. 实战应用场景与模板组合使用掌握了这些基础模板就像拥有了乐高积木。单独使用可以解决简单问题组合起来就能应对复杂挑战。场景一判断一个超大整数是否为质数如竞赛题直接使用Miller-Rabin 算法。这里给出一个针对 64 位整数确定性的实现def is_prime_miller_rabin(n: int) - bool: 确定性 Miller-Rabin适用于 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 # 足够覆盖 2^64 范围的测试底数集 for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]: if a % n 0: continue x pow(a, d, n) # 模幂运算 a^d mod n if x 1 or x n - 1: continue for _ in range(s - 1): x (x * x) % n if x n - 1: break else: # 循环正常结束未遇到 n-1 return False return True场景二求一个数的所有质因数之和结合快速质因数分解模板。def sum_of_prime_factors(n: int, min_prime: list) - int: 求质因数之和如 122^2*3和为2237 total 0 while n 1: p min_prime[n] total p n // p return total场景三求区间内所有数的因数个数这是一个经典问题。暴力枚举每个数再求因数个数会超时。正确做法是利用类似筛法的思想。def count_divisors_sieve(n: int) - list: 计算 1 到 n 每个数的正因数个数 div_count [0] * (n 1) for i in range(1, n 1): for j in range(i, n 1, i): # i 是 j 的因数 div_count[j] 1 return div_count这个算法的时间复杂度是 O(n log n)调和级数比 O(n√n) 的暴力法好很多。对于 n10^6 也能快速计算。5. 常见“坑点”与性能优化实录在实际编码和解题中我踩过不少坑也总结了一些优化技巧。坑点1整数溢出这是最隐蔽的 bug 之一。在i * i n的判断中当n接近整数类型上限时i*i可能会溢出。在 Python 中整数无限大没问题但在 C/Java 中对于大的n应该写成i n / i。在筛法标记i * i时同样可能溢出。安全的写法是if i n / i: break或者使用long long类型。坑点2边界条件处理n 2时不是质数。在枚举因数时n1的因数只有[1]n0则没有正因数。在质因数分解中循环结束后要判断n 1此时n本身就是一个质因子。性能优化技巧1空间换时间预处理是关键对于需要频繁查询质数、分解质因数的场景如解决一个包含多次询问的竞赛题预处理是王道。在程序开始时用线性筛一次性计算出足够大范围根据题目数据范围内的min_prime数组。后续所有的查询都是 O(1) 或 O(log n) 的常数时间操作。这比每次询问都重新运行试除法要快几个数量级。性能优化技巧2利用数学性质剪枝求一个数的所有因数时成对收集只需遍历到 √n。判断质数时先排除偶数再用6k±1规则。在分解质因数时单独处理2然后只遍历奇数。一个综合案例如何解决“求第N个质数”问题如果 N 很大比如第 1000000 个质数我们不能一直猜范围去筛。一个可靠的方法是根据质数定理第 N 个质数大约在N * ln(N) N * ln(ln(N))附近。可以估算一个上界limit。对这个limit使用埃拉托斯特尼筛法得到所有质数列表。直接取列表中的第 N-1 个元素列表从0开始索引。 如果筛法内存占用太大可以考虑使用分段筛法。最后我想分享的一点个人体会是不要死记硬背模板而要理解其背后的每一个“为什么”。比如为什么线性筛的内层循环需要p min_prime[i]就break理解了这一点你就能自己推导出这个算法甚至在需要时进行变通。这个“因数质数模板合集”是我工具箱里的常备武器希望它也能成为你解决相关问题时的得力助手。当你对这些基础工具了如指掌后你会发现很多看似复杂的数论问题其实都是这些基础操作的组合与延伸。