快速分解质因数诀窍

分解质因数。听起来像初中数学课的东西。但其实很有用。

比如你要算两个数的最大公约数或者最小公倍数，用它就很快。写程序的时候，有些算法问题也需要用到它。问题是，很多人觉得这个过程又慢又烦，特别是数字一大，就不知道从哪儿下手了。

我以前也觉得烦。后来做了一些编程题，被逼着找了些快一点的方法。这里说的不是那种需要超级计算机的加密算法，就是我们日常能遇到、笔和纸就能算出来的数字。

我们先从最基本的方法说起，就是短除法。这个方法最稳，不会出错，但效率不高。

举个例子，分解 360。

1. 先用最小的质数 2 去除。360 ÷ 2 = 180。
2. 180 还能被 2 整除，得 90。
3. 90 还能被 2 整除，得 45。
4. 45 不能被 2 整除了。那就试试下一个质数，3。45 ÷ 3 = 15。
5. 15 还能被 3 整除，得 5。
6. 5 本身就是质数了，结束。

所以，360 = 2 × 2 × 2 × 3 × 3 × 5，写成幂的形式就是 2³ × 3² × 5。

这个方法没问题，很扎实。但如果数字是 1764 呢？一步步用 2 去除，再用 3 去除，会有点慢。下面就是一些能让你快起来的诀窍。

第一个诀窍，也是最重要的：熟记一些基本整除规则。

这不是投机取巧，这是基本功。就像你学开车，总得先知道油门和刹车在哪。

• 能被 2 整除的数：这个最简单，看个位数是不是 0, 2, 4, 6, 8。是就行。
• 能被 3 整除的数：把这个数所有位上的数字加起来，如果加出来的和能被 3 整除，那这个数就能。比如 531，5 + 3 + 1 = 9。9 能被 3 整除，所以 531 肯定行。不信你算一下，531 ÷ 3 = 177。
• 能被 5 整除的数：看个位数是不是 0 或 5。
• 能被 11 整除的数：这个稍微复杂点，但很有用。从个位开始，奇数位上的数字和减去偶数位上的数字和，如果差是 0 或者 11 的倍数，这个数就能被 11 整除。比如 1353。个位是 3，十位是 5，百位是 3，千位是 1。奇数位是 (3 + 3) = 6。偶数位是 (5 + 1) = 6。差是 6 – 6 = 0。所以 1353 能被 11 整除。1353 ÷ 11 = 123。

至于 7 的整除规则，有，但是很麻烦，记起来的功夫还不如直接除一下试试快。所以我个人是不记的，直接动手算。这些规则的意义在于，你看到一个数，不用从 2 开始傻傻地试，而是可以直接判断出它有哪些“明显”的因数。

第二个诀窍：把大数拆成小数的乘积。

这是我最喜欢用的方法。不要总想着短除法那种线性的、一步接一步的思路。分解质因数更像是拆解一个机器，你可以从任何一个你看着顺眼的零件下手。

还是拿 360 举例子。我看到 360，第一反应不是去除以 2。我的第一反应是它等于 36 × 10。

这个拆解非常直观。然后问题就变成了分别分解 36 和 10，这就简单多了。

• 10 = 2 × 5。
• 36 = 6 × 6 = (2 × 3) × (2 × 3)。

好了，现在把所有零件（质因数）收集起来：两个 2，两个 3，一个 2，一个 5。合在一起就是三个 2，两个 3，一个 5。

所以 360 = 2³ × 3² × 5。

你看，这个过程比短除法快多了，也更符合直觉。你不是在机械地执行一个算法，而是在用你对数字的感觉去“破拆”它。

再来一个例子，比如 420。
看到 420，直接拆成 42 × 10。
10 = 2 × 5。
42 = 6 × 7 = 2 × 3 × 7。
合起来，420 = (2 × 3 × 7) × (2 × 5) = 2² × 3 × 5 × 7。几秒钟的事。

第三个诀窍：对平方数和立方数敏感。

有些数字是“伪装”起来的。它们看起来很大，但其实结构很简单。如果你能认出它们，就能省很多事。

比如分解 144。如果你用短除法，要除好几次 2 和 3。但如果你记得 12 × 12 = 144，问题就瞬间简化成了分解 12。
144 = 12² = (2² × 3)² = 2⁴ × 3²。

再比如 1000。
1000 = 10³ = (2 × 5)³ = 2³ × 5³。

熟记一些常见的平方数和立方数很有用。

• 平方数：121 (11²), 144 (12²), 169 (13²), 196 (14²), 225 (15²), 400 (20²), 625 (25²)。
• 立方数：125 (5³), 216 (6³), 343 (7³), 512 (8³), 729 (9³), 1000 (10³)。

这些数字就像是路上的熟人，你看到它们能直接打招呼，而不是还要上去盘问半天。

现在我们把这些诀窍组合起来，处理一个大一点的数：1764。

用短除法，你会：
1764 ÷ 2 = 882
882 ÷ 2 = 441
现在到了 441。你得去想它能被什么整除。用 3 的规则，4+4+1=9，能被 3 整除。
441 ÷ 3 = 147
1+4+7=12，还能被 3 整除。
147 ÷ 3 = 49
49 就很熟悉了，7 × 7。
所以 1764 = 2² × 3² × 7²。

这个过程不算太慢，但也不快。

现在用我们的诀窍来试试。
看到 1764，我首先注意到个位数是 4，它是一个平方数的特征（2²=4, 8²=64）。而且这个数感觉有点眼熟。40² = 1600，50² = 2500。1764 离 1600 不远。它的平方根的个位数应该是 2 或 8。我们可以试试 42。
42² = (40 + 2)² = 1600 + 2 * 40 * 2 + 4 = 1600 + 160 + 4 = 1764。
bingo！就是它。

既然 1764 = 42²，问题就简化成了分解 42。
42 = 6 × 7 = 2 × 3 × 7。
所以，1764 = (2 × 3 × 7)² = 2² × 3² × 7²。

这个思路是不是快得多？它依赖的是你对数字的观察和感觉，而不是纯粹的机械计算。

最后，还有一个问题：如果一个数很大，我怎么知道要试到什么时候？万一它本身就是个大质数呢？

这里有个关键的规则：你只需要测试到这个数的平方根为止。

为什么？很简单。假设一个数 N，它不是质数，那么它肯定可以写成 N = a × b 的形式。
如果 a 和 b 都大于 N 的平方根 (√N)，那么 a × b 就会大于 (√N) × (√N)，也就是大于 N。这和 N = a × b 矛盾了。
所以，a 和 b 里面，必然至少有一个是小于或等于 √N 的。

这意味着，如果你想分解 N，你只需要用小于等于 √N 的所有质数去试除。如果一个都除不尽，那就说明 N 本身就是一个质数。

举个例子，判断 211 是不是质数。
首先估算一下 √211。我们知道 14² = 196，15² = 225。所以 √211 在 14 和 15 之间。
根据规则，我们只需要测试所有小于 14 的质数就够了。这些质数是：2, 3, 5, 7, 11, 13。

1. 211 不是偶数，不能被 2 整除。
2. 2 + 1 + 1 = 4，不能被 3 整除。
3. 个位数不是 0 或 5，不能被 5 整除。
4. 211 ÷ 7 = 30 余 1，不能被 7 整除。
5. 211 ÷ 11 = 19 余 2，不能被 11 整除。
6. 211 ÷ 13 = 16 余 3，不能被 13 整除。

试完了所有小于 √211 的质数，都不能整除。那么我们就可以确定，211 是一个质数。你不需要再往后试 17、19 这些了。这个方法给你划定了一个明确的终点，避免了无休止的尝试。

总的来说，快速分解质因数靠的不是什么魔法，而是把几个简单有效的工具组合起来：
1. 用整除规则快速筛选掉小的质因数。
2. 用拆分乘积的思路把大问题变成小问题。
3. 对平方数和立方数保持敏感，一眼看穿它们的结构。
4. 用平方根规则确定试除的上限，避免做无用功。

多练习几次，这些思路就会变成你的本能。下次再碰到这种问题，就不会觉得头大了。