尧图网站建设 
1. 项目概述因数与质数程序员的数学基石在编程的世界里尤其是在算法竞赛、密码学基础以及日常的业务逻辑处理中因数和质数是两个绕不开的数学概念。它们看似基础却构成了无数复杂算法的基石。我见过太多新手也包括一些有经验的开发者在面对需要高效判断质数、分解质因数或者求取所有因数的场景时要么是暴力求解导致程序超时要么是代码冗长重复缺乏一个清晰、高效且可复用的模板。这个“因数质数模板合集”项目正是为了解决这个问题而生。它不是一份枯燥的数学教科书而是一个由实战经验凝结而成的代码工具箱。核心目标是为开发者特别是算法学习者和竞赛参与者提供一套经过验证的、可直接“复制粘贴”并稍作修改就能应对大部分相关问题的代码模块。从最基础的试除法判断质数到高效的埃拉托斯特尼筛法生成质数表再到利用试除法或Pollard-Rho算法进行质因数分解最后到枚举一个数的所有因数这个合集覆盖了从入门到进阶的常见需求。无论你是正在刷LeetCode上“计数质数”这道题还是在开发某个需要用到RSA加密原理的教学演示亦或是处理一些与数字性质相关的业务逻辑这个模板合集都能为你节省大量重新造轮子的时间让你更专注于问题本身的逻辑。2. 核心算法原理与模板设计思路2.1 质数判定从暴力到优化质数判定的核心是对于一个大于1的自然数n如果它不能被2到n-1之间的任何整数整除那么它就是质数。最直接的实现就是试除法。2.1.1 基础试除法模板这是最直观的方法但效率较低时间复杂度为 O(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注意这个方法仅适用于教学理解或极小的n比如n 10^4在实际应用和算法题中几乎一定会超时。2.1.2 优化试除法模板一个关键的数学优化是如果n能被某个大于sqrt(n)的数整除那么其对应的因子必然小于sqrt(n)。因此我们只需要检查到int(sqrt(n))即可。时间复杂度降为 O(√n)。import math def is_prime(n: int) - bool: if n 2: return False # 单独处理偶数加速 if n % 2 0: return n 2 # 从3开始步长为2只检查奇数 upper_limit int(math.isqrt(n)) # Python 3.8 使用 isqrt 更精确高效 for i in range(3, upper_limit 1, 2): if n % i 0: return False return True实操心得math.isqrt(n)是求整数平方根的最佳方式比int(n**0.5)更精确、更快。先判断偶数然后只遍历奇数因子这是一个非常有效的常数优化。这个模板可以处理n高达10^12左右的质数判定在1秒内对于算法竞赛中的大部分单点质数判断题目已经足够。2.2 质数筛法批量生产的艺术当需要判断或列出从1到N的所有质数时使用筛法比逐个调用is_prime函数高效得多。最经典的是埃拉托斯特尼筛法。2.2.1 埃氏筛模板原理是从2开始将每个质数的所有倍数标记为合数。def sieve_of_eratosthenes(n: int): 返回一个布尔列表 is_prime其中 is_prime[i] 表示 i 是否为质数 (0 i n)。 if n 2: return [False] * (n 1) is_prime [True] * (n 1) is_prime[0:2] [False, False] # 0和1不是质数 for i in range(2, int(n ** 0.5) 1): if is_prime[i]: # 从 i*i 开始标记因为 i*(i-1), i*(i-2)... 已经被更小的质数标记过了 step i start i * i is_prime[start: n1: step] [False] * (((n - start) // step) 1) return is_prime2.2.2 线性筛欧拉筛模板埃氏筛的一个缺点是有些合数会被重复标记例如6会被2和3都标记。线性筛通过保证每个合数只被其最小质因子标记一次达到O(n)的时间复杂度并且能同时得到每个数的最小质因子这在后续质因数分解时非常有用。def linear_sieve(n: int): 返回两个列表 is_prime: 布尔列表is_prime[i] 表示 i 是否为质数。 primes: 存储所有找到的质数。 min_prime_factor: 每个数的最小质因子质数的最小质因子是它自身。 is_prime [True] * (n 1) primes [] min_prime_factor [0] * (n 1) # 0表示未处理或为质数对于质数后续会赋值为自身 for i in range(2, n 1): if is_prime[i]: primes.append(i) min_prime_factor[i] i for p in primes: if p * i n: break is_prime[p * i] False min_prime_factor[p * i] p # 关键如果 i 能被当前质数 p 整除则停止内层循环。 # 这保证了每个合数只被其最小质因子标记一次。 if i % p 0: break return is_prime, primes, min_prime_factor方案选型考量埃氏筛代码简单内存访问模式相对连续在N很大如10^7时由于其常数小实际运行速度可能比线性筛更快适合仅需要质数布尔表的情况。线性筛理论复杂度更优能额外得到最小质因子表适合需要频繁进行质因数分解的场景例如多次查询不同数的质因数。当N在10^6到10^7量级时两者均可可根据后续需求选择。2.3 质因数分解拆解数字的DNA质因数分解是将一个合数分解为若干个质数相乘的形式。这是很多数论问题的基础。2.3.1 试除法分解模板基于优化试除法的思想逐个尝试质因子。def prime_factorization_trial(n: int): 返回一个列表每个元素为 (质因子, 指数) 的元组。 factors [] # 处理因子2 cnt 0 while n % 2 0: n // 2 cnt 1 if cnt 0: factors.append((2, cnt)) # 处理奇数因子 p 3 while p * p n: cnt 0 while n % p 0: n // p cnt 1 if cnt 0: factors.append((p, cnt)) p 2 # 如果最后剩下的n大于1它本身就是一个质数 if n 1: factors.append((n, 1)) return factors2.3.2 基于线性筛最小质因子表的分解模板如果已经通过线性筛预处理了min_prime_factor数组那么质因数分解可以做到单次查询 O(log n)。def prime_factorization_using_lpf(n: int, min_prime_factor: list): 利用最小质因子表快速分解。min_prime_factor 来自 linear_sieve 函数。 factors [] while n 1: p min_prime_factor[n] cnt 0 while n % p 0: n // p cnt 1 factors.append((p, cnt)) return factors实操心得试除法模板通用性强无需预处理适合单次或少量次数的分解。如果题目需要频繁地对多个数进行质因数分解比如10^5次查询每个数 10^6那么先使用线性筛预处理出min_prime_factor表再用第二个模板进行分解总效率会高得多。分解结果的(质因子, 指数)格式非常有用可以轻松计算约数个数、约数和等数论函数。2.4 枚举所有因数构建数字的“朋友圈”给定一个正整数n列出它的所有正因数。一个简单的方法是遍历1到sqrt(n)。2.4.1 因数枚举模板def get_factors(n: int): 返回 n 的所有正因数列表未排序。 factors [] i 1 while i * i n: if n % i 0: factors.append(i) # 避免重复添加平方根 if i ! n // i: factors.append(n // i) i 1 return factors # 如果需要排序可以返回 sorted(factors)原理与优化核心思想与优化试除法一致成对地找出因数。当i能整除n时i和n//i都是n的因数。循环终止条件是i * i n这保证了我们只遍历到sqrt(n)。注意处理i n // i的情况即n是完全平方数避免同一个因数被添加两次。2.4.2 通过质因数分解生成所有因数当需要按顺序获取因数或者n的质因数分解形式已知时可以通过回溯法生成所有因数。这种方法生成的因数默认是有序的如果质因子列表有序。def get_factors_from_prime_factors(prime_factors): 根据质因数分解结果生成所有因数。 prime_factors: 列表元素为 (质因子, 指数)。 例如prime_factors [(2,2), (3,1)] 表示 n 2^2 * 3^1 12。 def dfs(idx, current_product): if idx len(prime_factors): factors.append(current_product) return p, exp prime_factors[idx] for e in range(exp 1): dfs(idx 1, current_product * (p ** e)) factors [] dfs(0, 1) return sorted(factors) # 回溯生成的可能无序排序后返回方案选型考量方法一直接枚举简单直接适用于大多数情况尤其是单次查询。方法二分解后生成在以下情况更有优势已经得到了质因数分解的结果。n非常大但其质因子个数很少例如大质数的乘积直接枚举sqrt(n)可能很慢而质因子组合爆炸的规模较小。需要有序的因数列表。3. 模板集成与实战应用场景3.1 模板合集完整代码示例将上述核心模板整合到一个类或模块中便于管理。这里提供一个面向对象的示例但也可以直接作为函数集使用。import math from typing import List, Tuple class PrimeUtils: 因数与质数工具集 staticmethod def is_prime(n: int) - bool: 优化试除法判断质数适用于 n 10^12 的单点判断。 if n 2: return False if n % 2 0: return n 2 limit math.isqrt(n) for i in range(3, limit 1, 2): if n % i 0: return False return True staticmethod def sieve_eratosthenes(n: int) - List[bool]: 埃拉托斯特尼筛法返回 is_prime 列表。 if n 2: return [False] * (n 1) is_prime [True] * (n 1) is_prime[0:2] [False, False] limit math.isqrt(n) for i in range(2, limit 1): if is_prime[i]: step i start i * i # 使用切片赋值批量标记比循环快 is_prime[start: n1: step] [False] * (((n - start) // step) 1) return is_prime staticmethod def linear_sieve(n: int) - Tuple[List[bool], List[int], List[int]]: 线性筛欧拉筛返回是否质数质数列表最小质因子列表。 is_prime [True] * (n 1) primes [] min_prime_factor [0] * (n 1) for i in range(2, n 1): if is_prime[i]: primes.append(i) min_prime_factor[i] i for p in primes: composite p * i if composite n: break is_prime[composite] False min_prime_factor[composite] p if i % p 0: break return is_prime, primes, min_prime_factor staticmethod def prime_factorization(n: int, min_prime_factor: List[int] None) - List[Tuple[int, int]]: 质因数分解。 如果提供了 min_prime_factor来自 linear_sieve则使用快速分解。 否则使用试除法。 factors [] if min_prime_factor is not None and n len(min_prime_factor): # 快速分解模式 while n 1: p min_prime_factor[n] cnt 0 while n % p 0: n // p cnt 1 factors.append((p, cnt)) else: # 试除法模式 cnt 0 while n % 2 0: n // 2 cnt 1 if cnt: factors.append((2, cnt)) p 3 while p * p n: cnt 0 while n % p 0: n // p cnt 1 if cnt: factors.append((p, cnt)) p 2 if n 1: factors.append((n, 1)) return factors staticmethod def get_factors(n: int) - List[int]: 枚举 n 的所有正因数。 factors [] i 1 while i * i n: if n % i 0: factors.append(i) if i ! n // i: factors.append(n // i) i 1 return factors # 注意未排序 staticmethod def get_factors_sorted(n: int) - List[int]: 枚举 n 的所有正因数并排序。 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 factors3.2 典型应用场景与调用示例场景一解决LeetCode 204. 计数质数题目要求统计所有小于非负整数n的质数的数量。这正是筛法的用武之地。class Solution: def countPrimes(self, n: int) - int: if n 2: return 0 # 使用埃氏筛 is_prime PrimeUtils.sieve_eratosthenes(n-1) # 注意是小于n # 计算True的个数减去0和1的位置它们为False return sum(is_prime) # 因为is_prime[0]和[1]已经是False场景二求一个数的约数个数与约数和数论公式若n p1^a1 * p2^a2 * ... * pk^ak则约数个数d(n) (a11)*(a21)*...*(ak1)约数和σ(n) (p1^(a11)-1)/(p1-1) * (p2^(a21)-1)/(p2-1) * ... * (pk^(ak1)-1)/(pk-1)def divisor_count_and_sum(n: int): 返回约数个数和约数和。 factors PrimeUtils.prime_factorization(n) d 1 sigma 1 for p, a in factors: d * (a 1) # 计算 (p^(a1) - 1) / (p - 1) 即等比数列和 sigma * (pow(p, a 1) - 1) // (p - 1) return d, sigma # 示例 n 12 2^2 * 3^1 # 约数个数 (21)*(11)6 # 约数和 (2^3-1)/(2-1) * (3^2-1)/(3-1) 7 * 4 28 print(divisor_count_and_sum(12)) # 输出: (6, 28)场景三判断友好数对如果两个正整数每个数的所有真因数除了自身以外的因数之和等于对方则称它们为友好数对。例如 (220, 284)。def sum_of_proper_divisors(n: int) - int: 计算n的所有真因数之和。 factors PrimeUtils.get_factors_sorted(n) # 真因数不包括n本身 return sum(factors[:-1]) def is_amicable(a: int, b: int) - bool: return sum_of_proper_divisors(a) b and sum_of_proper_divisors(b) a and a ! b print(is_amicable(220, 284)) # 输出: True4. 性能优化、边界处理与常见陷阱4.1 性能优化技巧预处理与查询分离在算法竞赛中如果题目需要频繁查询例如10^5次某个范围内的数是否为质数或者需要其最小质因子那么在程序开始时用线性筛一次性预处理整个范围比如10^6是最高效的策略。这避免了每次查询都重复计算。利用位运算和数组优化在埃氏筛中可以使用bytearray或bitset在Python中可用bitarray库来存储布尔数组大幅减少内存占用并可能提升缓存命中率。def sieve_bit(n: int): 使用bytearray的埃氏筛内存更友好。 if n 2: return bytearray(b\x00) * (n 1) is_prime bytearray(b\x01) * (n 1) is_prime[0:2] b\x00\x00 limit int(n ** 0.5) for i in range(2, limit 1): if is_prime[i]: step i start i * i is_prime[start: n1: step] b\x00 * (((n - start) // step) 1) return is_prime大数质数判定对于超过10^12的单点大数质数判定优化试除法可能仍然不够快。此时需要更高级的算法如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 # 写 n-1 为 d * 2^r 的形式 d n - 1 r 0 while d % 2 0: d // 2 r 1 # 对于 64 位整数这些底数足以进行确定性测试 for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]: if a % n 0: continue x pow(a, d, n) if x 1 or x n - 1: continue for _ in range(r - 1): x (x * x) % n if x n - 1: break else: return False return True4.2 边界条件与陷阱输入为0或1在质数判断和因数枚举中0和1需要特殊处理。它们既不是质数也不是合数。get_factors(1)应返回[1]而get_factors(0)在数学上定义是无穷多个通常在实际编程中会避免或抛出异常。整数溢出在计算i * i作为循环终止条件时如果i很大接近2^31i * i可能会溢出32位整数。在Python中整数无此问题但在C/Java中需要特别注意应使用i n / i进行比较。浮点数精度使用int(n ** 0.5)或int(math.sqrt(n))求平方根时对于极大的完全平方数如10^18浮点数运算可能产生精度误差导致平方根取整少1。始终优先使用math.isqrt(n)。筛法的内存限制埃氏筛或线性筛需要O(n)的内存。当n达到10^8时一个布尔列表需要约100MB内存可能超出限制。此时可以考虑使用分段筛或者使用位压缩技术。因数的顺序get_factors函数返回的因数列表是无序的。如果业务需要有序的因数务必调用sorted()或使用get_factors_sorted。回溯法生成的因数列表通常也是无序的需要排序。4.3 常见问题排查速查表问题现象可能原因解决方案质数判断对于大数如9999999967超时使用了未优化的试除法循环到n-1改用优化试除法循环到sqrt(n)或Miller-Rabin测试。筛法程序在n10^7时内存占用巨大使用普通的list of bool每个元素占一个字节。改用bytearray或array(b)或者使用位运算压缩每个位表示一个数。因数枚举结果中有重复的数字如n9得到[1,3,3,9]循环中未处理i n // i的情况。在添加n // i前判断i ! n // i。质因数分解结果错误漏掉了某个质因子试除法循环后忘记处理最后剩下的n。在试除法循环结束后检查if n 1:将其作为最后一个质因子加入。使用线性筛后分解质因数时进入死循环min_prime_factor表预处理的范围小于待分解的数n。确保预处理的范围N大于等于所有待分解的n。或者在分解函数中加入范围检查并回退到试除法。计算约数和时得到浮点数或错误结果直接使用(p**(a1)-1)/(p-1)产生了浮点数除法。使用整数除法//即(p**(a1) - 1) // (p - 1)。5. 模板的扩展与变种掌握了基础模板后可以应对大部分情况。但某些特殊场景需要进一步的变种。5.1 区间筛法问题求区间[L, R]内所有质数其中1 L R 10^12但R-L 10^6。无法直接筛到10^12。 思路先用普通筛法筛出sqrt(R)以内的所有质数然后用这些质数去标记区间[L, R]内的合数。def segmented_sieve(L: int, R: int): 返回区间[L, R]内所有质数的列表。 if L R: return [] limit int(math.isqrt(R)) # 第一步筛出[2, limit]内的质数 base_primes [] is_prime_small [True] * (limit 1) is_prime_small[0:2] [False, False] for i in range(2, limit 1): if is_prime_small[i]: base_primes.append(i) step i start i * i is_prime_small[start: limit1: step] [False] * (((limit - start) // step) 1) # 第二步用base_primes标记[L, R]区间 is_prime_seg [True] * (R - L 1) if L 1: # 1不是质数 is_prime_seg[0] False for p in base_primes: # 找到大于等于L的第一个p的倍数 start max(p * p, ((L p - 1) // p) * p) for j in range(start, R 1, p): is_prime_seg[j - L] False # 收集结果 primes [] for i, flag in enumerate(is_prime_seg): if flag: primes.append(L i) return primes5.2 枚举因数对有时我们需要以“因数对”的形式来使用因数例如在计算矩形面积或排列组合时。def iterate_factor_pairs(n: int): 生成所有 (a, b) 使得 a * b n 且 a b。 a 1 while a * a n: if n % a 0: b n // a yield a, b # 使用生成器节省内存 a 1 # 使用 for factor_a, factor_b in iterate_factor_pairs(12): print(factor_a, factor_b) # (1,12), (2,6), (3,4)5.3 统计质数个数素数计数函数π(n)的近似对于极大的n如10^12无法直接筛可以用Meissel-Lehmer算法等高级算法在亚线性时间内计算质数个数。这属于数论的高级内容有现成的模板代码理解其思想后可以直接使用。将这些模板理解透彻并熟练运用足以解决编程中95%以上与因数、质数相关的初级和中级问题。关键在于根据具体场景数据范围、查询次数、内存限制选择最合适的工具并注意处理好边界条件。 因数与质数算法模板合集：从质数判定到因数枚举的实战指南
1. 项目概述因数与质数程序员的数学基石在编程的世界里尤其是在算法竞赛、密码学基础以及日常的业务逻辑处理中因数和质数是两个绕不开的数学概念。它们看似基础却构成了无数复杂算法的基石。我见过太多新手也包括一些有经验的开发者在面对需要高效判断质数、分解质因数或者求取所有因数的场景时要么是暴力求解导致程序超时要么是代码冗长重复缺乏一个清晰、高效且可复用的模板。这个“因数质数模板合集”项目正是为了解决这个问题而生。它不是一份枯燥的数学教科书而是一个由实战经验凝结而成的代码工具箱。核心目标是为开发者特别是算法学习者和竞赛参与者提供一套经过验证的、可直接“复制粘贴”并稍作修改就能应对大部分相关问题的代码模块。从最基础的试除法判断质数到高效的埃拉托斯特尼筛法生成质数表再到利用试除法或Pollard-Rho算法进行质因数分解最后到枚举一个数的所有因数这个合集覆盖了从入门到进阶的常见需求。无论你是正在刷LeetCode上“计数质数”这道题还是在开发某个需要用到RSA加密原理的教学演示亦或是处理一些与数字性质相关的业务逻辑这个模板合集都能为你节省大量重新造轮子的时间让你更专注于问题本身的逻辑。2. 核心算法原理与模板设计思路2.1 质数判定从暴力到优化质数判定的核心是对于一个大于1的自然数n如果它不能被2到n-1之间的任何整数整除那么它就是质数。最直接的实现就是试除法。2.1.1 基础试除法模板这是最直观的方法但效率较低时间复杂度为 O(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注意这个方法仅适用于教学理解或极小的n比如n 10^4在实际应用和算法题中几乎一定会超时。2.1.2 优化试除法模板一个关键的数学优化是如果n能被某个大于sqrt(n)的数整除那么其对应的因子必然小于sqrt(n)。因此我们只需要检查到int(sqrt(n))即可。时间复杂度降为 O(√n)。import math def is_prime(n: int) - bool: if n 2: return False # 单独处理偶数加速 if n % 2 0: return n 2 # 从3开始步长为2只检查奇数 upper_limit int(math.isqrt(n)) # Python 3.8 使用 isqrt 更精确高效 for i in range(3, upper_limit 1, 2): if n % i 0: return False return True实操心得math.isqrt(n)是求整数平方根的最佳方式比int(n**0.5)更精确、更快。先判断偶数然后只遍历奇数因子这是一个非常有效的常数优化。这个模板可以处理n高达10^12左右的质数判定在1秒内对于算法竞赛中的大部分单点质数判断题目已经足够。2.2 质数筛法批量生产的艺术当需要判断或列出从1到N的所有质数时使用筛法比逐个调用is_prime函数高效得多。最经典的是埃拉托斯特尼筛法。2.2.1 埃氏筛模板原理是从2开始将每个质数的所有倍数标记为合数。def sieve_of_eratosthenes(n: int): 返回一个布尔列表 is_prime其中 is_prime[i] 表示 i 是否为质数 (0 i n)。 if n 2: return [False] * (n 1) is_prime [True] * (n 1) is_prime[0:2] [False, False] # 0和1不是质数 for i in range(2, int(n ** 0.5) 1): if is_prime[i]: # 从 i*i 开始标记因为 i*(i-1), i*(i-2)... 已经被更小的质数标记过了 step i start i * i is_prime[start: n1: step] [False] * (((n - start) // step) 1) return is_prime2.2.2 线性筛欧拉筛模板埃氏筛的一个缺点是有些合数会被重复标记例如6会被2和3都标记。线性筛通过保证每个合数只被其最小质因子标记一次达到O(n)的时间复杂度并且能同时得到每个数的最小质因子这在后续质因数分解时非常有用。def linear_sieve(n: int): 返回两个列表 is_prime: 布尔列表is_prime[i] 表示 i 是否为质数。 primes: 存储所有找到的质数。 min_prime_factor: 每个数的最小质因子质数的最小质因子是它自身。 is_prime [True] * (n 1) primes [] min_prime_factor [0] * (n 1) # 0表示未处理或为质数对于质数后续会赋值为自身 for i in range(2, n 1): if is_prime[i]: primes.append(i) min_prime_factor[i] i for p in primes: if p * i n: break is_prime[p * i] False min_prime_factor[p * i] p # 关键如果 i 能被当前质数 p 整除则停止内层循环。 # 这保证了每个合数只被其最小质因子标记一次。 if i % p 0: break return is_prime, primes, min_prime_factor方案选型考量埃氏筛代码简单内存访问模式相对连续在N很大如10^7时由于其常数小实际运行速度可能比线性筛更快适合仅需要质数布尔表的情况。线性筛理论复杂度更优能额外得到最小质因子表适合需要频繁进行质因数分解的场景例如多次查询不同数的质因数。当N在10^6到10^7量级时两者均可可根据后续需求选择。2.3 质因数分解拆解数字的DNA质因数分解是将一个合数分解为若干个质数相乘的形式。这是很多数论问题的基础。2.3.1 试除法分解模板基于优化试除法的思想逐个尝试质因子。def prime_factorization_trial(n: int): 返回一个列表每个元素为 (质因子, 指数) 的元组。 factors [] # 处理因子2 cnt 0 while n % 2 0: n // 2 cnt 1 if cnt 0: factors.append((2, cnt)) # 处理奇数因子 p 3 while p * p n: cnt 0 while n % p 0: n // p cnt 1 if cnt 0: factors.append((p, cnt)) p 2 # 如果最后剩下的n大于1它本身就是一个质数 if n 1: factors.append((n, 1)) return factors2.3.2 基于线性筛最小质因子表的分解模板如果已经通过线性筛预处理了min_prime_factor数组那么质因数分解可以做到单次查询 O(log n)。def prime_factorization_using_lpf(n: int, min_prime_factor: list): 利用最小质因子表快速分解。min_prime_factor 来自 linear_sieve 函数。 factors [] while n 1: p min_prime_factor[n] cnt 0 while n % p 0: n // p cnt 1 factors.append((p, cnt)) return factors实操心得试除法模板通用性强无需预处理适合单次或少量次数的分解。如果题目需要频繁地对多个数进行质因数分解比如10^5次查询每个数 10^6那么先使用线性筛预处理出min_prime_factor表再用第二个模板进行分解总效率会高得多。分解结果的(质因子, 指数)格式非常有用可以轻松计算约数个数、约数和等数论函数。2.4 枚举所有因数构建数字的“朋友圈”给定一个正整数n列出它的所有正因数。一个简单的方法是遍历1到sqrt(n)。2.4.1 因数枚举模板def get_factors(n: int): 返回 n 的所有正因数列表未排序。 factors [] i 1 while i * i n: if n % i 0: factors.append(i) # 避免重复添加平方根 if i ! n // i: factors.append(n // i) i 1 return factors # 如果需要排序可以返回 sorted(factors)原理与优化核心思想与优化试除法一致成对地找出因数。当i能整除n时i和n//i都是n的因数。循环终止条件是i * i n这保证了我们只遍历到sqrt(n)。注意处理i n // i的情况即n是完全平方数避免同一个因数被添加两次。2.4.2 通过质因数分解生成所有因数当需要按顺序获取因数或者n的质因数分解形式已知时可以通过回溯法生成所有因数。这种方法生成的因数默认是有序的如果质因子列表有序。def get_factors_from_prime_factors(prime_factors): 根据质因数分解结果生成所有因数。 prime_factors: 列表元素为 (质因子, 指数)。 例如prime_factors [(2,2), (3,1)] 表示 n 2^2 * 3^1 12。 def dfs(idx, current_product): if idx len(prime_factors): factors.append(current_product) return p, exp prime_factors[idx] for e in range(exp 1): dfs(idx 1, current_product * (p ** e)) factors [] dfs(0, 1) return sorted(factors) # 回溯生成的可能无序排序后返回方案选型考量方法一直接枚举简单直接适用于大多数情况尤其是单次查询。方法二分解后生成在以下情况更有优势已经得到了质因数分解的结果。n非常大但其质因子个数很少例如大质数的乘积直接枚举sqrt(n)可能很慢而质因子组合爆炸的规模较小。需要有序的因数列表。3. 模板集成与实战应用场景3.1 模板合集完整代码示例将上述核心模板整合到一个类或模块中便于管理。这里提供一个面向对象的示例但也可以直接作为函数集使用。import math from typing import List, Tuple class PrimeUtils: 因数与质数工具集 staticmethod def is_prime(n: int) - bool: 优化试除法判断质数适用于 n 10^12 的单点判断。 if n 2: return False if n % 2 0: return n 2 limit math.isqrt(n) for i in range(3, limit 1, 2): if n % i 0: return False return True staticmethod def sieve_eratosthenes(n: int) - List[bool]: 埃拉托斯特尼筛法返回 is_prime 列表。 if n 2: return [False] * (n 1) is_prime [True] * (n 1) is_prime[0:2] [False, False] limit math.isqrt(n) for i in range(2, limit 1): if is_prime[i]: step i start i * i # 使用切片赋值批量标记比循环快 is_prime[start: n1: step] [False] * (((n - start) // step) 1) return is_prime staticmethod def linear_sieve(n: int) - Tuple[List[bool], List[int], List[int]]: 线性筛欧拉筛返回是否质数质数列表最小质因子列表。 is_prime [True] * (n 1) primes [] min_prime_factor [0] * (n 1) for i in range(2, n 1): if is_prime[i]: primes.append(i) min_prime_factor[i] i for p in primes: composite p * i if composite n: break is_prime[composite] False min_prime_factor[composite] p if i % p 0: break return is_prime, primes, min_prime_factor staticmethod def prime_factorization(n: int, min_prime_factor: List[int] None) - List[Tuple[int, int]]: 质因数分解。 如果提供了 min_prime_factor来自 linear_sieve则使用快速分解。 否则使用试除法。 factors [] if min_prime_factor is not None and n len(min_prime_factor): # 快速分解模式 while n 1: p min_prime_factor[n] cnt 0 while n % p 0: n // p cnt 1 factors.append((p, cnt)) else: # 试除法模式 cnt 0 while n % 2 0: n // 2 cnt 1 if cnt: factors.append((2, cnt)) p 3 while p * p n: cnt 0 while n % p 0: n // p cnt 1 if cnt: factors.append((p, cnt)) p 2 if n 1: factors.append((n, 1)) return factors staticmethod def get_factors(n: int) - List[int]: 枚举 n 的所有正因数。 factors [] i 1 while i * i n: if n % i 0: factors.append(i) if i ! n // i: factors.append(n // i) i 1 return factors # 注意未排序 staticmethod def get_factors_sorted(n: int) - List[int]: 枚举 n 的所有正因数并排序。 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 factors3.2 典型应用场景与调用示例场景一解决LeetCode 204. 计数质数题目要求统计所有小于非负整数n的质数的数量。这正是筛法的用武之地。class Solution: def countPrimes(self, n: int) - int: if n 2: return 0 # 使用埃氏筛 is_prime PrimeUtils.sieve_eratosthenes(n-1) # 注意是小于n # 计算True的个数减去0和1的位置它们为False return sum(is_prime) # 因为is_prime[0]和[1]已经是False场景二求一个数的约数个数与约数和数论公式若n p1^a1 * p2^a2 * ... * pk^ak则约数个数d(n) (a11)*(a21)*...*(ak1)约数和σ(n) (p1^(a11)-1)/(p1-1) * (p2^(a21)-1)/(p2-1) * ... * (pk^(ak1)-1)/(pk-1)def divisor_count_and_sum(n: int): 返回约数个数和约数和。 factors PrimeUtils.prime_factorization(n) d 1 sigma 1 for p, a in factors: d * (a 1) # 计算 (p^(a1) - 1) / (p - 1) 即等比数列和 sigma * (pow(p, a 1) - 1) // (p - 1) return d, sigma # 示例 n 12 2^2 * 3^1 # 约数个数 (21)*(11)6 # 约数和 (2^3-1)/(2-1) * (3^2-1)/(3-1) 7 * 4 28 print(divisor_count_and_sum(12)) # 输出: (6, 28)场景三判断友好数对如果两个正整数每个数的所有真因数除了自身以外的因数之和等于对方则称它们为友好数对。例如 (220, 284)。def sum_of_proper_divisors(n: int) - int: 计算n的所有真因数之和。 factors PrimeUtils.get_factors_sorted(n) # 真因数不包括n本身 return sum(factors[:-1]) def is_amicable(a: int, b: int) - bool: return sum_of_proper_divisors(a) b and sum_of_proper_divisors(b) a and a ! b print(is_amicable(220, 284)) # 输出: True4. 性能优化、边界处理与常见陷阱4.1 性能优化技巧预处理与查询分离在算法竞赛中如果题目需要频繁查询例如10^5次某个范围内的数是否为质数或者需要其最小质因子那么在程序开始时用线性筛一次性预处理整个范围比如10^6是最高效的策略。这避免了每次查询都重复计算。利用位运算和数组优化在埃氏筛中可以使用bytearray或bitset在Python中可用bitarray库来存储布尔数组大幅减少内存占用并可能提升缓存命中率。def sieve_bit(n: int): 使用bytearray的埃氏筛内存更友好。 if n 2: return bytearray(b\x00) * (n 1) is_prime bytearray(b\x01) * (n 1) is_prime[0:2] b\x00\x00 limit int(n ** 0.5) for i in range(2, limit 1): if is_prime[i]: step i start i * i is_prime[start: n1: step] b\x00 * (((n - start) // step) 1) return is_prime大数质数判定对于超过10^12的单点大数质数判定优化试除法可能仍然不够快。此时需要更高级的算法如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 # 写 n-1 为 d * 2^r 的形式 d n - 1 r 0 while d % 2 0: d // 2 r 1 # 对于 64 位整数这些底数足以进行确定性测试 for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]: if a % n 0: continue x pow(a, d, n) if x 1 or x n - 1: continue for _ in range(r - 1): x (x * x) % n if x n - 1: break else: return False return True4.2 边界条件与陷阱输入为0或1在质数判断和因数枚举中0和1需要特殊处理。它们既不是质数也不是合数。get_factors(1)应返回[1]而get_factors(0)在数学上定义是无穷多个通常在实际编程中会避免或抛出异常。整数溢出在计算i * i作为循环终止条件时如果i很大接近2^31i * i可能会溢出32位整数。在Python中整数无此问题但在C/Java中需要特别注意应使用i n / i进行比较。浮点数精度使用int(n ** 0.5)或int(math.sqrt(n))求平方根时对于极大的完全平方数如10^18浮点数运算可能产生精度误差导致平方根取整少1。始终优先使用math.isqrt(n)。筛法的内存限制埃氏筛或线性筛需要O(n)的内存。当n达到10^8时一个布尔列表需要约100MB内存可能超出限制。此时可以考虑使用分段筛或者使用位压缩技术。因数的顺序get_factors函数返回的因数列表是无序的。如果业务需要有序的因数务必调用sorted()或使用get_factors_sorted。回溯法生成的因数列表通常也是无序的需要排序。4.3 常见问题排查速查表问题现象可能原因解决方案质数判断对于大数如9999999967超时使用了未优化的试除法循环到n-1改用优化试除法循环到sqrt(n)或Miller-Rabin测试。筛法程序在n10^7时内存占用巨大使用普通的list of bool每个元素占一个字节。改用bytearray或array(b)或者使用位运算压缩每个位表示一个数。因数枚举结果中有重复的数字如n9得到[1,3,3,9]循环中未处理i n // i的情况。在添加n // i前判断i ! n // i。质因数分解结果错误漏掉了某个质因子试除法循环后忘记处理最后剩下的n。在试除法循环结束后检查if n 1:将其作为最后一个质因子加入。使用线性筛后分解质因数时进入死循环min_prime_factor表预处理的范围小于待分解的数n。确保预处理的范围N大于等于所有待分解的n。或者在分解函数中加入范围检查并回退到试除法。计算约数和时得到浮点数或错误结果直接使用(p**(a1)-1)/(p-1)产生了浮点数除法。使用整数除法//即(p**(a1) - 1) // (p - 1)。5. 模板的扩展与变种掌握了基础模板后可以应对大部分情况。但某些特殊场景需要进一步的变种。5.1 区间筛法问题求区间[L, R]内所有质数其中1 L R 10^12但R-L 10^6。无法直接筛到10^12。 思路先用普通筛法筛出sqrt(R)以内的所有质数然后用这些质数去标记区间[L, R]内的合数。def segmented_sieve(L: int, R: int): 返回区间[L, R]内所有质数的列表。 if L R: return [] limit int(math.isqrt(R)) # 第一步筛出[2, limit]内的质数 base_primes [] is_prime_small [True] * (limit 1) is_prime_small[0:2] [False, False] for i in range(2, limit 1): if is_prime_small[i]: base_primes.append(i) step i start i * i is_prime_small[start: limit1: step] [False] * (((limit - start) // step) 1) # 第二步用base_primes标记[L, R]区间 is_prime_seg [True] * (R - L 1) if L 1: # 1不是质数 is_prime_seg[0] False for p in base_primes: # 找到大于等于L的第一个p的倍数 start max(p * p, ((L p - 1) // p) * p) for j in range(start, R 1, p): is_prime_seg[j - L] False # 收集结果 primes [] for i, flag in enumerate(is_prime_seg): if flag: primes.append(L i) return primes5.2 枚举因数对有时我们需要以“因数对”的形式来使用因数例如在计算矩形面积或排列组合时。def iterate_factor_pairs(n: int): 生成所有 (a, b) 使得 a * b n 且 a b。 a 1 while a * a n: if n % a 0: b n // a yield a, b # 使用生成器节省内存 a 1 # 使用 for factor_a, factor_b in iterate_factor_pairs(12): print(factor_a, factor_b) # (1,12), (2,6), (3,4)5.3 统计质数个数素数计数函数π(n)的近似对于极大的n如10^12无法直接筛可以用Meissel-Lehmer算法等高级算法在亚线性时间内计算质数个数。这属于数论的高级内容有现成的模板代码理解其思想后可以直接使用。将这些模板理解透彻并熟练运用足以解决编程中95%以上与因数、质数相关的初级和中级问题。关键在于根据具体场景数据范围、查询次数、内存限制选择最合适的工具并注意处理好边界条件。