从暴力遍历到平方根优化：高效求解整数所有因子的算法详解

1. 从一道经典面试题说起你真的会找“所有因子”吗“求一个数的所有因子”这听起来像一道小学数学题简单到让人不屑一顾。不就是找出所有能整除这个数的正整数吗很多程序员朋友的第一反应是这还不简单从1遍历到这个数本身挨个试除能整除的就是因子。代码可能三五行就写完了。但如果你在技术面试或者算法竞赛中给出这个答案大概率会被面试官追问“时间复杂度是多少当这个数是10^12甚至更大时你的程序要跑多久” 或者 “有没有更高效的方法如何避免重复计算和排序” 这时候问题就不再那么简单了。它从一个基础的编程练习变成了一个考察数学思维、算法优化和边界处理能力的综合问题。今天我们就来彻底拆解这个“简单”问题背后的门道从最朴素的暴力法到基于数论的高效算法再到工程实践中的各种坑和优化技巧让你不仅会写代码更能理解为什么这么写。2. 因子分解的数学基石理解问题的本质在动手写代码之前我们必须先回到数学定义上把“因子”这个概念吃透。这决定了我们算法的上限和优化方向。2.1 因子的定义与性质对于一个正整数n如果存在另一个正整数d使得n % d 0即n能被d整除那么d就是n的一个因子或约数。n本身和 1 总是它的因子。这里有几个关键性质是高效算法的核心成对出现如果d是n的因子那么n / d也必然是n的因子。例如对于n12因子2和6就是一对3和4是另一对。对称轴在平方根根据成对出现的性质当我们找到较小的因子d时我们同时找到了较大的因子n/d。这两者以sqrt(n)为对称轴。当d小于sqrt(n)时n/d大于sqrt(n)当d等于sqrt(n)时n/d也等于sqrt(n)此时d是单独一个即n是完全平方数。因子个数有限一个数的因子个数是有限的并且通常远小于这个数本身。例如n10^12这个数很大但它的因子个数可能只有几百个。我们的算法应该努力去接近这个“因子个数”的量级而不是“数值大小”的量级。2.2 算法效率的衡量标准我们通常用时间复杂度来衡量算法效率。对于这个问题朴素暴力法遍历1到n时间复杂度是O(n)。当n10^9时循环十亿次在现代计算机上也可能需要数秒甚至更久这是不可接受的。优化遍历法利用“对称轴在平方根”的性质只需遍历1到sqrt(n)时间复杂度降为O(sqrt(n))。当n10^12时sqrt(n)10^6只需循环一百万次瞬间完成。这是质的飞跃。更高级的算法如果需要频繁地对极大整数进行因子分解可能会用到 Pollard-Rho 算法、二次筛法等但这些已超出本文“求所有因子”的范畴属于“质因数分解”领域。我们求所有因子通常是在质因数分解的结果上组合得到的。理解了这些我们就知道主流的优化方向就是围绕sqrt(n)做文章。3. 从青铜到王者四种求因子算法的实现与对比接下来我们由浅入深看看几种不同层次的实现方法。我会用 Python 语言示例因为它清晰易懂但思路适用于任何语言。3.1 方法一最朴素的暴力遍历青铜这是最直观也是最慢的方法。def get_factors_naive(n): factors [] for i in range(1, n 1): # 遍历1到n if n % i 0: factors.append(i) return factors # 示例 print(get_factors_naive(12)) # 输出: [1, 2, 3, 4, 6, 12]时间复杂度O(n)。缺点n稍大比如超过10^7效率就急剧下降。绝不推荐在实际项目或面试中使用此方法它仅仅用于理解问题。3.2 方法二利用平方根优化黄金这是最常用且实用的方法利用了因子成对出现的性质。def get_factors_sqrt(n): factors [] i 1 # 只遍历到 sqrt(n)注意要包含等于的情况所以用 i*i n while i * i n: if n % i 0: factors.append(i) # 添加较小的因子 i if i ! n // i: # 避免添加重复的因子当n是完全平方数时 factors.append(n // i) # 添加对应的较大因子 n//i i 1 factors.sort() # 因为因子是成对添加的顺序是乱的需要排序 return factors # 示例 print(get_factors_sqrt(12)) # 输出: [1, 2, 3, 4, 6, 12] print(get_factors_sqrt(16)) # 输出: [1, 2, 4, 8, 16]核心逻辑解析循环条件i*i n等价于i sqrt(n)但避免了计算浮点数平方根的开销和精度问题。当n % i 0时我们找到了一个因子对i和n//i。判断i ! n//i是为了处理完全平方数的情况。例如n16当i4时n//i也是4如果不加判断因子4会被添加两次。最后需要对结果列表排序因为我们先添加所有小因子再穿插添加它们对应的大因子顺序是[1, 12, 2, 6, 3, 4]排序后得到有序列表。时间复杂度循环部分O(sqrt(n))排序部分O(k log k)其中k是因子个数。由于k通常远小于sqrt(n)整体效率可以近似看作O(sqrt(n))。注意这里有一个常见的坑。很多人会用for i in range(1, int(math.sqrt(n)) 1)来循环。这看起来更简洁但存在两个问题一是对于极大的n如 Python 大整数math.sqrt可能先转换成浮点数导致精度丢失甚至溢出错误二是int()转换和range生成在n极大时也有开销。while i*i n使用纯整数运算更加稳健和高效。3.3 方法三先质因数分解再组合生成铂金这是理论上更优雅的方法尤其当需要多次获取一个数的因子或者需要获取诸如“因子个数”、“因子和”等其他信息时先进行质因数分解是更优解。思路对n进行质因数分解得到质因数及其幂次的映射。例如60 2^2 * 3^1 * 5^1。所有因子都是这些质因数幂次的组合。对于2^2可以取2^0, 2^1, 2^2对于3^1可以取3^0, 3^1对于5^1可以取5^0, 5^1。将这些选择进行笛卡尔积相乘就得到了所有因子。def prime_factors(n): 返回 n 的质因数分解字典如 60 - {2:2, 3:1, 5:1} factors_dict {} d 2 # 仍然只需要检查到 sqrt(n) while d * d n: while n % d 0: # 当d是因子时除尽它 factors_dict[d] factors_dict.get(d, 0) 1 n // d d 1 if d 2 else 2 # 2以后只检查奇数一个小优化 if n 1: # 最后剩下的n如果是大于1的质数 factors_dict[n] factors_dict.get(n, 0) 1 return factors_dict def get_factors_from_prime(factors_dict): 从质因数分解字典生成所有因子 factors [1] for prime, exp in factors_dict.items(): # 对于当前质因数prime其可能取值为 prime^0, prime^1, ..., prime^exp current_prime_powers [prime ** i for i in range(exp 1)] # 将现有因子列表与当前质因数的所有幂次相乘组合 new_factors [] for existing_factor in factors: for power in current_prime_powers: new_factors.append(existing_factor * power) factors new_factors factors.sort() return factors # 组合使用 n 60 pf prime_factors(60) # {2: 2, 3: 1, 5: 1} factors get_factors_from_prime(pf) print(factors) # 输出: [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]优点可复用性强一旦得到质因数分解结果可以快速计算因子个数(e11)*(e21)*...、因子和等。适用于极大数如果结合更高效的质因数分解算法如 Pollard-Rho可以处理非常大的整数。逻辑清晰严格遵循了因子的数学定义。缺点对于单纯“求所有因子”的任务代码比方法二复杂。质因数分解本身在最坏情况下n是质数也需要O(sqrt(n))的时间与方法二持平。3.4 方法四追求极致的性能优化王者在算法竞赛或对性能有极致要求的场景我们还可以在方法二的基础上进行微优化。def get_factors_fast(n): 快速求因子避免使用列表追加和排序 lo_factors [] hi_factors [] i 1 while i * i n: if n % i 0: lo_factors.append(i) j n // i if i ! j: hi_factors.append(j) i 1 # hi_factors 是大因子是逆序的反转后拼接 hi_factors.reverse() return lo_factors hi_factors # 示例 print(get_factors_fast(12)) # 输出: [1, 2, 3, 4, 6, 12]优化点双列表存储用lo_factors存储小于等于sqrt(n)的因子小因子用hi_factors存储大于sqrt(n)的因子大因子。这样在添加时小因子是顺序添加大因子是逆序添加因为i增大时n//i减小。避免最后排序最后只需将逆序的hi_factors反转然后与小因子列表拼接结果就是有序的。这省去了对整个结果列表进行O(k log k)的排序操作变为O(k)的反转和拼接操作。这个优化在因子数量k很大时比如几千个会有可感知的性能提升。虽然时间复杂度记号仍是O(sqrt(n))但常数更优。4. 实战中的坑与经验技巧掌握了核心算法在实际编码中还会遇到一些细节问题。下面是我踩过的一些坑和总结的经验。4.1 边界条件与特殊输入处理永远不要相信输入。你的函数应该能优雅地处理各种边界情况。def get_factors_robust(n): 健壮的求因子函数 if not isinstance(n, int) or n 0: raise ValueError(输入必须为正整数) if n 1: return [1] # 1的因子只有它自己 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处理的边界情况非正整数输入抛出明确错误避免后续计算出现意外。输入为1这是一个特例循环条件while i*i 1在i1时成立但i ! n//i不成立1 ! 1为假所以只会添加一次1。但显式处理能让逻辑更清晰。大整数输入Python 原生支持大整数所以i*i不会溢出。但在 C/Java 等语言中要小心i*i可能溢出可以使用i n/i作为循环条件。4.2 性能瓶颈分析与优化选择选择哪种方法这取决于你的具体场景。场景一单次查询n在10^12以内无脑选择方法二平方根优化。它实现简单效率足够10^6次循环在现代 CPU 上就是一瞬间的事。场景二需要频繁获取同一个数n的因子或者还需要因子个数、因子和等信息考虑方法三质因数分解。你可以把质因数分解的结果缓存起来后续所有衍生计算都极快。场景三算法竞赛追求极限速度使用方法四双列表优化。并且注意用本地变量如sqrt_n int(n**0.5)和for循环代替while可能还有微弱的提升但要注意浮点数精度问题。场景四n是超过10^18的极大整数朴素平方根法O(sqrt(n))也失效了sqrt(10^18)10^9十亿次循环也慢。这时求“所有因子”通常不现实因子可能也很多问题往往会转化为“质因数分解”或“判断是否为质数”需要使用Miller-Rabin 素性测试、Pollard-Rho 因数分解等随机算法。4.3 一个常见的误解因子 vs 质因子我见过不少初学者混淆这两个概念。所有因子12的所有因子是[1, 2, 3, 4, 6, 12]。质因子12的质因子是[2, 3]通常表示为2^2 * 3。一定要明确需求。如果题目要求的是“质因数分解”那你最终输出的应该是类似{2:2, 3:1}的字典或[2, 2, 3]的列表而不是所有因子的列表。4.4 扩展应用求多个数的公因子/最大公约数“求一个数的因子”是基础。更常见的扩展问题是“求两个数的所有公因子”或“最大公约数GCD”。思路两个数a和b的公因子一定是它们最大公约数gcd(a, b)的因子。所以问题转化为计算g gcd(a, b)使用高效的欧几里得算法。求g的所有因子。import math def get_common_factors(a, b): 求a和b的所有正公因子 g math.gcd(a, b) # Python内置了gcd函数非常快 return get_factors_sqrt(g) # 复用我们之前写的函数 print(get_common_factors(12, 18)) # 输出: [1, 2, 3, 6]这个方法高效且优雅避免了分别求两个大数的因子再取交集的笨重操作。5. 在不同语言中的实现要点虽然算法思想通用但在不同编程语言中实现时需要注意语言特性的差异。5.1 Python 实现如上述示例Python 的优势在于大整数支持和简洁的语法。注意使用//进行整数除法。使用math.isqrt(n)Python 3.8可以安全地计算整数平方根比int(n**0.5)更精确。列表推导式可以让代码更简洁但可能牺牲一点可读性def get_factors_pythonic(n): from math import isqrt factors [] for i in range(1, isqrt(n) 1): if n % i 0: factors.append(i) if (j : n // i) ! i: # 海象运算符 Python 3.8 factors.append(j) factors.sort() return factors5.2 Java 实现在 Java 中要特别注意整数范围避免溢出。import java.util.ArrayList; import java.util.Collections; import java.util.List; public class FactorFinder { public static ListInteger getFactors(int n) { if (n 0) throw new IllegalArgumentException(n must be positive); ListInteger factors new ArrayList(); ListInteger largeFactors new ArrayList(); // 使用 i n / i 避免 i*i 可能导致的溢出 for (int i 1; i n / i; i) { if (n % i 0) { factors.add(i); if (i ! n / i) { largeFactors.add(n / i); } } } Collections.reverse(largeFactors); // 大因子列表是逆序的需要反转 factors.addAll(largeFactors); return factors; } }要点循环条件用i n / i比i * i n更安全因为i * i可能超出int范围2^31-1导致溢出变成负数。对于long类型同理。5.3 C 实现C 的实现与 Java 类似但可以利用vector的reserve方法预分配空间来提升性能。#include vector #include algorithm #include cmath std::vectorint get_factors(int n) { if (n 0) return {}; std::vectorint factors; std::vectorint large_factors; // 预分配空间避免多次动态扩容。因子个数不会超过 2*sqrt(n) factors.reserve(std::sqrt(n) * 2); large_factors.reserve(std::sqrt(n)); for (int i 1; i n / i; i) { if (n % i 0) { factors.push_back(i); if (i ! n / i) { large_factors.push_back(n / i); } } } std::reverse(large_factors.begin(), large_factors.end()); factors.insert(factors.end(), large_factors.begin(), large_factors.end()); return factors; }6. 总结与个人体会回过头看“求一个数的所有因子”这个问题就像编程世界里的“Hello World”入门简单但深究下去却串联起了循环优化、数学性质应用、边界处理、算法选择等多个编程核心知识点。我个人的体会是这类基础问题往往是面试官考察候选人基本功和思维深度的试金石。在平时练习中不要满足于写出一个能跑通的朴素解法。多问自己几个问题它的瓶颈在哪里数据范围扩大怎么办有没有更本质的数学性质可以利用比如从O(n)到O(sqrt(n))的优化就是利用了因子成对出现且对称分布在平方根两侧这一关键性质。这种“寻找问题的特殊结构来优化通用算法”的思维在解决更复杂的问题时至关重要。最后分享一个我常用的检查清单在实现这类功能时总会过一遍输入验证正整数零和一如何处理循环边界是用i*i n还是i sqrt(n)注意数据类型的溢出。去重处理完全平方数的平方根因子是否会被添加两次结果顺序是否需要有序输出是在过程中维护顺序还是最后排序性能考量对于可能的重复查询是否有缓存空间换时间的可能扩展思考这个问题能否泛化例如求多个数的公因子、求因子个数、求因子和等。把每一个简单的问题都挖深、吃透积累下来的就是扎实的内功。下次再遇到类似问题你就能一眼看穿本质快速给出稳健而高效的解决方案了。