质因数分解

如何将一个数分解为质数构成要素

每个大于 1 的整数都可以分解为唯一的一组质数相乘 — 即其质因数分解。 输入一个整数，此计算器会立即计算出该分解结果，以及该数本身是否为质数。

计算公式

算术基本定理保证每个大于 1 的整数 N 都恰好只有一种质因数分解方式（不考虑因数书写的先后顺序）：

$$\vA{N} = \vB{p_1}^{\vC{a_1}} \times \vB{p_2}^{\vC{a_2}} \times \cdots \times \vB{p_k}^{\vC{a_k}}$$

其中每个 $\vB{p_i}$ 都是一个不同的质数，每个 $\vC{a_i}$ 表示该质数能整除 N 的次数。

此计算器使用试除法求出该分解：从 2 开始，反复检查每个数字是否能整除剩余部分，如果能，就将其除出（并计数次数），然后移至下一个候选数。一旦某个候选数的平方超过了剩余部分，那么剩下的数本身必定是质数 — 因为任何更小的因数早已被找出：

$$\text{若 } \vD{d}^2 > \vE{\text{剩余值}}, \text{则 } \vE{\text{剩余值}} \text{ 是质数}$$

举例说明

求 360 的质因数分解：

1. 360 ÷ 2 = 180，÷ 2 = 90，÷ 2 = 45（2 能整除 3 次；45 是奇数，故继续）。
2. 45 ÷ 3 = 15，÷ 3 = 5（3 能整除 2 次；5 不能再被 3 整除）。
3. 剩下 5，且没有更大的除数的平方 ≤ 5，因此 5 本身就是质数。
4. 结果：2³ × 3² × 5。

需要考虑的关键因素

• 每个质因数分解都是唯一的 — 这正是算术基本定理所保证的。 无论一个数是如何被分解的，其 质因数分解结果始终相同（不考虑因数书写的先后顺序），这正是质因数分解在数论中如此基础的原 因。
• 质因数分解是手动求最大公因数或最小公倍数背后的原理。 直接比较两个数的质因数分解，就能 直接看出它们的最大公因数（共有的质因数，取较低的共同指数）和最小公倍数（所有质因数，取较 高的指数）— 具体比较可参见最大公因数/最小公倍数计算器。
• 随着位数增加，分解大数在计算上会变得困难得多，这正是某些加密方法的基础。 试除法（此处 所用的方法）对于人们通常手动输入的数字效果很好，但要分解一个有数百位数字的超大数字，即使 对强大的计算机来说也可能在计算上不可行 — 这种困难正是 RSA 加密安全性的基础。
• 一个质数恰好只有一个质因数：即它本身，指数为一。 这正是为什么本计算器「该数是否为质 数」的判断可以直接由分解过程得出 — 如果试除法从未找到小于该数自身平方根的因数，那么这个 数就没有除自身以外的其他分解方式。

常见误区

• 把质因数分解和完整的因数列表混为一谈。 12 的因数是 1、2、3、4、6 和 12，但它的质因数 分解只是 2² × 3 — 质因数分解只保留质数构成要素，而不是所有能整除的数字。
• 把 1 当作质数。 按照定义，质数恰好有两个不同的因数（1 和它本身）— 而 1 只有一个因数， 所以它既不是质数也不是合数，也永远不会出现在任何质因数分解中。
• 忽略重复出现的质因数。 8 的质因数分解是 2³，而不仅仅是「2」— 忘记某个质数整除的次数， 会改变该分解实际所代表的数字。

实用小知识

• 需要两个数的最大公因数或最小公倍数，而不是单个数自身的因数？最大公因数与最小公倍数计算器 可直 接比较两个数的质因数分解。
• 正在把一个分数化简到最简形式？分数计算器 使用的正是此计算器所找到的相同公 共质因数。
• 需要处理的是一个非常大或非常小的数字？科学记数法计算器 可在标准计数法 和科学计数法之间转换。