1. 从一道题说起为什么“最大质因数”值得单独写一篇第一次接触“求解最大质因数”这个问题是在帮一个朋友准备编程面试的时候。题目很直白给定一个正整数找出它所有质因数中最大的那个。比如 13195 的最大质因数是 29600851475143 的最大质因数是 6857。看起来简单但真正动手写代码的时候你会发现这里面藏着不少门道——从最朴素的试除法到 Pollard‘s Rho 这种进阶算法中间的选择空间比想象中大得多。这篇文章适合谁看如果你正在准备技术面试或者刚学完基础语法想找一道题练手又或者你单纯对“怎么把一个数拆干净”这件事感到好奇那接下来的内容应该能帮到你。我会从最笨的办法开始一步步优化把每一步的取舍逻辑讲清楚最后给出可以直接复制运行的代码。整个过程不依赖任何特殊库Python 标准库就能跑。需要提前说明的是质因数分解本身是一个经典问题它的应用场景远不止做题——密码学里的 RSA 加密、数论研究、甚至某些哈希算法的设计底层都跟质因数分解的难度有关。所以花时间搞懂它性价比很高。2. 先把概念理清楚质因数到底是什么2.1 质数与因数的基本定义质数素数是指大于 1 的自然数中除了 1 和它本身之外没有其他因数的数。比如 2、3、5、7、11、13 都是质数而 4、6、8、9 不是。因数则是能整除某个数的数比如 12 的因数有 1、2、3、4、6、12。把这两个概念合在一起质因数就是“既是质数又是某个数的因数”的数。举个例子12 的因数有 1、2、3、4、6、12其中质数只有 2 和 3所以 12 的质因数是 2 和 3。注意这里说的是“质因数”而不是“质因数分解”——前者是一个集合后者是把一个数写成质因数乘积的形式比如 12 2² × 3。2.2 为什么最大质因数比最小质因数更难求求最小质因数其实很简单从 2 开始往上试第一个能整除的就是答案。但最大质因数不一样你没法从大到小试——因为一个数的因数分布是不对称的大的因数往往藏在后面。比如 600851475143它的最小质因数是 71但最大质因数是 6857差了将近一百倍。这就引出了一个关键思路要找到最大质因数最有效的办法不是从大往小找而是从小往大除把小的质因数一个个除掉最后剩下的那个就是最大的质因数。这个思路是后面所有优化算法的基石理解了它后面的代码就都好懂了。2.3 一个容易踩的坑1 和负数怎么处理在实际写代码的时候有几个边界情况必须提前想清楚。第一1 没有质因数因为质因数要求大于 1所以输入 1 的时候应该返回什么通常我们会返回 None 或者抛异常具体看你的接口设计。第二负数怎么办负数的因数里也有质数但通常这类题目默认输入是正整数如果非要处理负数可以先取绝对值再算。第三0 呢0 能被任何非零整数整除所以它的质因数集合是无限的直接排除掉。提示在面试中遇到这类题目先跟面试官确认输入范围比直接写代码更能体现你的严谨性。3. 最朴素的试除法能跑但别拿去面试3.1 从 2 到 n-1 逐个试最直观的做法是对于给定的数 n从 2 开始一直到 n-1逐个检查能不能整除 n。如果能整除再判断这个因数是不是质数如果是就记录下来。最后返回记录中最大的那个。def is_prime(x): if x 2: return False for i in range(2, int(x ** 0.5) 1): if x % i 0: return False return True def largest_prime_factor_naive(n): if n 2: return None largest None for i in range(2, n): if n % i 0 and is_prime(i): largest i return largest这段代码逻辑没问题但效率极低。假设 n 600851475143循环次数接近六千亿次就算用最快的计算机也要跑很久。所以这个版本只适合用来理解题意实际使用必须优化。3.2 第一个优化只试到平方根一个数的因数总是成对出现的。如果 d 是 n 的因数那么 n/d 也是 n 的因数。这对因数中较小的那个一定小于等于 √n。所以判断一个数是不是质数时只需要试到 √n 就够了。这个优化把 is_prime 的复杂度从 O(n) 降到了 O(√n)。但对于“找最大质因数”这个问题光优化 is_prime 还不够因为外层循环还是从 2 到 n-1。我们需要换个思路。3.3 第二个优化边除边缩小范围回到前面说的核心思路从小到大找质因数找到一个就从 n 里除掉它。这样 n 会越来越小循环的上界也跟着变小。具体做法是从 i 2 开始。如果 i 能整除 n就把 n 除以 i直到不能整除为止同时记录 i 是质因数。i 加 1继续。当 i * i n 时停止此时如果 n 1那么 n 本身就是最后一个质因数。def largest_prime_factor_better(n): if n 2: return None factor 2 last_factor None while factor * factor n: if n % factor 0: last_factor factor while n % factor 0: n // factor factor 1 if n 1: last_factor n return last_factor这个版本比朴素版快了几个数量级。以 600851475143 为例循环只需要跑到 6857 左右因为每次找到一个质因数后 n 都会大幅缩小。实测下来这个版本在普通笔记本上跑一次不到一毫秒。4. 还能更快吗进阶算法与取舍分析4.1 6k ± 1 优化跳过明显的合数上面那个版本虽然快但 factor 每次只加 1会检查很多明显不是质数的数比如 4、6、8、9。一个常见的优化是除了 2 和 3 之外所有质数都可以写成 6k ± 1 的形式k 是正整数。所以我们可以先处理 2 和 3然后从 5 开始每次加 2 或 4 交替。def largest_prime_factor_6k(n): if n 2: return None last_factor None for p in (2, 3): while n % p 0: last_factor p n // p k 1 while (6 * k - 1) ** 2 n: for p in (6 * k - 1, 6 * k 1): while n % p 0: last_factor p n // p k 1 if n 1: last_factor n return last_factor这个版本比上一个版本大约快 2 到 3 倍因为跳过了 2/3 的合数。但代码可读性稍微下降了一点实际项目中要不要用取决于你对性能的要求。4.2 Pollard‘s Rho大数分解的利器如果输入的数非常大比如上百位上面这些方法都不够用了。这时候需要用到 Pollard’s Rho 算法它的核心思想是利用生日悖论和 Floyd 判圈算法在 O(n^(1/4)) 的期望时间内找到一个因子。import math import random def gcd(a, b): while b: a, b b, a % b return a def pollard_rho(n): if n % 2 0: return 2 if n % 3 0: return 3 while True: c random.randint(1, n - 1) f lambda x: (x * x c) % n x, y, d 2, 2, 1 while d 1: x f(x) y f(f(y)) d gcd(abs(x - y), n) if d ! n: return d def largest_prime_factor_rho(n): if n 2: return None if is_prime(n): return n d pollard_rho(n) return max(largest_prime_factor_rho(d), largest_prime_factor_rho(n // d))Pollard‘s Rho 的代码明显复杂很多而且需要配合 Miller-Rabin 素性测试才能完整工作。对于一般的面试题或者日常使用前面那个 6k ± 1 的版本已经足够了。除非你确实要处理很大的数否则没必要上这个。4.3 不同算法的适用场景对比算法版本时间复杂度适用场景代码复杂度朴素试除法O(n)教学演示低平方根优化O(√n)小规模数据低边除边缩小O(√n) 但常数更小一般面试题中6k ± 1 优化约 O(√n / 3)中等规模数据中Pollard’s Rho期望 O(n^(1/4))大数分解高选择哪个版本取决于你的具体需求。如果只是做一道题边除边缩小的版本最平衡如果追求极致性能且不介意代码复杂度可以上 6k ± 1如果处理的是密码学级别的大数那就必须用 Pollard‘s Rho 加上 Miller-Rabin。5. 实测中的意外情况与排查记录5.1 输入 1 和 0 时的返回值问题第一次写测试用例的时候我顺手把 1 和 0 也扔进去了结果代码直接返回 None但调用方没有处理这个情况导致后面报错。后来我养成了一个习惯所有涉及数学计算的函数先把边界情况列出来明确每个边界返回什么。对于“最大质因数”这个问题我的约定是n 2 时返回 None调用方必须显式处理 None。5.2 大数运算中的整数溢出在 Python 里不用担心整数溢出因为 Python 的 int 是任意精度的。但如果你用 C 或 Java 写同样的逻辑就要注意 n 的类型。比如 600851475143 这个数用 32 位 int 存不下必须用 64 位 long long。我在帮朋友看代码的时候就遇到过因为用了 int 导致结果错误的情况。5.3 性能测试中的意外发现我拿几个不同的数做了性能对比结果发现一个有意思的现象对于某些数比如 2 的幂次如 2^30边除边缩小的版本几乎瞬间完成因为第一次循环就把所有 2 都除掉了。但对于质数本身比如 999999999989循环要跑到 √n 才能确认它是质数耗时明显更长。这说明算法的实际表现跟输入数据的分布有很大关系不能只看理论复杂度。注意如果你在面试中写的是边除边缩小的版本面试官可能会追问“如果输入是一个很大的质数怎么办”这时候你可以回答“对于质数确实需要试到平方根但这是不可避免的因为判断质数本身就需要这么多操作”。6. 可以直接抄作业的完整代码与使用建议6.1 推荐版本兼顾性能与可读性综合来看我最推荐的版本是边除边缩小加上 6k ± 1 优化代码不算太复杂性能也足够好。下面是完整代码可以直接复制使用def largest_prime_factor(n): 返回正整数 n 的最大质因数。 如果 n 2返回 None。 if n 2: return None last_factor None for p in (2, 3): while n % p 0: last_factor p n // p k 1 while (6 * k - 1) ** 2 n: for p in (6 * k - 1, 6 * k 1): while n % p 0: last_factor p n // p k 1 if n 1: last_factor n return last_factor6.2 测试用例与验证方法写完代码后我习惯用几组已知答案的测试用例来验证assert largest_prime_factor(13195) 29 assert largest_prime_factor(600851475143) 6857 assert largest_prime_factor(2) 2 assert largest_prime_factor(1) is None assert largest_prime_factor(0) is None assert largest_prime_factor(97) 97 assert largest_prime_factor(100) 5这几组用例覆盖了普通合数、大数、质数、边界值等常见情况。每次修改代码后跑一遍能快速发现回归问题。6.3 实际使用中的几个小技巧第一如果你需要频繁调用这个函数可以考虑加一个缓存把已经算过的结果存起来。第二如果输入的数范围不大可以预先用筛法打出质数表然后直接用质数表来试除速度会更快。第三如果只是判断一个数是不是质数不需要找最大质因数直接用 Miller-Rabin 测试比试除法快得多。我在实际项目中遇到过一次需要批量处理几万个数的场景当时就是先用筛法打出 10^6 以内的质数表然后用这些质数去试除整体速度比逐个用 6k ± 1 快了不少。所以具体用哪种方法还是要看你的数据规模和调用频率。最后再分享一个小经验写这类数学算法的时候先把数学原理想清楚再动手写代码比直接对着题目硬写要快得多。我见过不少人一上来就开始敲键盘结果写到一半发现思路不对又得推倒重来。花五分钟把思路理清楚能省下半小时的调试时间。