质因数分解

又称:分解质因数、短除法、标准分解式

质因数分解是把一个大于 1 的整数写成若干质数连乘的形式,比如 360 = 2 × 2 × 2 × 3 × 3 × 5,写成幂的标准式就是 360 = 2³ × 3² × 5。算术基本定理保证:每个大于 1 的整数,都能唯一地这样分解(不计顺序)。

分解方法是「短除法」:从最小的质数 2 开始试除,能整除就一直除到除不尽,再换 3、5、7 下一个质数,直到商变成 1。以 360 为例:连除 3 个 2 得 45,再连除 2 个 3 得 5,最后除以 5 得 1,所以 360 = 2³ × 3² × 5。一个实用加速技巧:只要试除到 √n 就够了,若到这里还没除尽,剩下的商本身必然是一个大质数。

分解完能派生出很多信息。最漂亮的是约数个数公式:把标准式里每个指数加 1 再相乘就得到。360 = 2³ × 3² × 5,约数个数 = (3+1)(2+1)(1+1) = 4 × 3 × 2 = 24 个。原理是每个质因数在约数里可取 0 到该指数次幂,各自独立组合。质因数分解还是求最大公约数(取公共质因数的最低次幂)和最小公倍数(取最高次幂)的理论基础,也是约分、通分背后的原理。

相关术语

相关计算器