别再死记硬背筛法了！三种质因数分解算法（迭代/递归/打表）的保姆级性能对比与选择指南

质因数分解算法实战：从暴力迭代到打表优化的性能博弈

在算法竞赛和面试中，质因数分解是一个看似基础却暗藏玄机的问题。很多开发者习惯性地套用教科书上的递归解法，却在实际应用中遭遇性能瓶颈或栈溢出危机。本文将带您深入三种主流实现方案（迭代法、递归法、打表法）的性能差异，通过实测数据揭示不同场景下的最优选择。

1. 算法原理与实现对比

1.1 迭代法：最朴实的暴力美学

迭代法采用最直接的思路——从最小的质数2开始，逐个尝试整除目标数。每次找到能整除的质数后，记录该质数的指数，并将目标数除以该质数，直到目标数变为1。

def factorize_iterative(n): factors = {} divisor = 2 while n > 1: while n % divisor == 0: factors[divisor] = factors.get(divisor, 0) + 1 n //= divisor divisor += 1 return factors

性能特点：

• 时间复杂度：O(√n) 最坏情况（当n为质数时）
• 空间复杂度：O(1) 仅需常数空间存储临时变量
• 优势：实现简单，不依赖额外空间
• 劣势：对大质数效率较低

1.2 递归法：优雅但危险的策略

递归法将问题分解为子问题：找到一个质因数后，递归处理商的部分。

def factorize_recursive(n, start=2, factors=None): if factors is None: factors = {} if n == 1: return factors for i in range(start, int(n**0.5)+1): if n % i == 0: factors[i] = factors.get(i, 0) + 1 return factorize_recursive(n//i, i, factors) factors[n] = factors.get(n, 0) + 1 return factors

性能特点：

• 时间复杂度：与迭代法相同，O(√n)
• 空间复杂度：O(d) 其中d为递归深度
• 优势：代码结构清晰，符合数学归纳思维
• 劣势：存在栈溢出风险，Python默认递归深度约1000层

警告：在C++等语言中，默认栈空间较小，递归深度超过几千层就可能引发栈溢出。即使是Python，处理极大数字时也可能遇到递归深度限制。

1.3 打表法：空间换时间的经典案例

打表法预先计算并存储一定范围内的质数，利用这些质数来加速分解过程。

def generate_primes(limit): sieve = [True] * (limit + 1) sieve[0] = sieve[1] = False for num in range(2, int(limit**0.5)+1): if sieve[num]: sieve[num*num::num] = [False] * len(sieve[num*num::num]) return [i for i, is_prime in enumerate(sieve) if is_prime] def factorize_with_primes(n, primes): factors = {} for p in primes: if p*p > n: break while n % p == 0: factors[p] = factors.get(p, 0) + 1 n //= p if n > 1: factors[n] = 1 return factors

性能特点：

• 预处理时间复杂度：O(n log log n) 使用埃拉托斯特尼筛法
• 查询时间复杂度：O(π(√n)) ≈ O(√n / ln n) 其中π(x)为小于x的质数数量
• 空间复杂度：O(n) 存储质数表
• 优势：重复查询时效率极高
• 劣势：预处理耗时，内存占用大

2. 性能基准测试与数据分析

我们使用Python的timeit模块对三种算法进行测试，环境为Intel i7-1185G7 @ 3.0GHz，Python 3.9.7。

2.1 小数字测试（n < 10^6）

*打表法测试使用预先生成的10^6以内的质数表（78498个质数），预处理时间约120ms

小数字结论：

• 对于小数字，打表法优势明显（快2-3倍）
• 当n为质数时，迭代法和递归法性能急剧下降
• 递归法因函数调用开销略慢于迭代法

2.2 大数字测试（n ≥ 10^9）

**使用10^6以内的质数表，更大的质数需要额外处理

大数字结论：

• 递归法对大质数极易栈溢出
• 打表法在质数表覆盖范围内表现卓越
• 对于完全由小质数组成的大数（如2^40），所有方法都很快

3. 算法选择决策树

根据测试结果，我们总结出以下选择策略：

1. 是否需要处理极大数字（>10^12）？

   • 是 → 考虑迭代法（递归法有栈溢出风险）
   • 否 → 进入下一步

2. 是否需要重复分解多个数字？

   • 是 → 打表法（预处理成本可分摊）
   • 否 → 进入下一步

3. 目标数字是否可能为大质数？

   • 是 → 考虑带优化的迭代法（试除到√n即可）
   • 否 → 任意方法均可

4. 是否有严格的内存限制？

   • 是 → 迭代法
   • 否 → 打表法

4. 高级优化技巧与实践建议

4.1 混合策略：结合打表与迭代

对于极大数字，可以先使用质数表处理小因子，剩余部分再用迭代法：

def factorize_hybrid(n, primes): factors = {} # 先用质数表处理 for p in primes: if p*p > n: break while n % p == 0: factors[p] = factors.get(p, 0) + 1 n //= p # 剩余部分用迭代法 if n > 1: if n <= primes[-1]**2: factors[n] = factors.get(n, 0) + 1 else: # 大数迭代 divisor = primes[-1] + (1 if primes[-1] % 2 == 0 else 0) while divisor*divisor <= n: while n % divisor == 0: factors[divisor] = factors.get(divisor, 0) + 1 n //= divisor divisor += 2 if n > 1: factors[n] = factors.get(n, 0) + 1 return factors

4.2 预生成质数表的技巧

• 分段筛法：处理极大范围时，可分块生成质数表
• 位压缩存储：用位图代替布尔数组，节省75%内存
• 质数缓存：将生成的质数表序列化保存，避免重复计算

import bitarray def sieve_bitarray(limit): sieve = bitarray.bitarray(limit+1) sieve.setall(True) sieve[0] = sieve[1] = False for i in range(2, int(limit**0.5)+1): if sieve[i]: sieve[i*i::i] = False return sieve

4.3 竞赛中的实用技巧

• 预先计算常用质数：如10^6以内的质数表仅约78KB（压缩后更小）
• 快速素性测试：对极大数先用Miller-Rabin测试判断是否为质数
• 并行分解：对多核系统，可将不同范围的试除分配给不同线程

from concurrent.futures import ThreadPoolExecutor def parallel_factorize(n, threads=4): def worker(start, end): factors = {} for i in range(start, end, 2): if n % i == 0: k = 0 while n % i == 0: k += 1 n //= i factors[i] = k return factors with ThreadPoolExecutor(max_workers=threads) as executor: futures = [] chunk = int(n**0.5) // threads for t in range(threads): start = 3 + t*chunk end = start + chunk if t != threads-1 else int(n**0.5)+1 futures.append(executor.submit(worker, start, end)) result = {} for future in futures: result.update(future.result()) return result

在实际项目中使用质因数分解时，我发现混合策略往往能取得最佳平衡。对于OJ系统，打表法通常是首选，因为测试用例经常重复使用小质数。而在处理用户输入的任意大数时，带有预筛的迭代法则更为稳健。