如何理解质因数分解的结果
下表展示了几个常见数的质因数分解，用来说明指数记号的用法。
| 数值 | 质因数分解 | 约数个数 |
|---|---|---|
| 12 | 2² × 3 | 6 |
| 100 | 2² × 5² | 9 |
| 360 | 2³ × 3² × 5 | 24 |
| 17（一个质数） | 17（本身，指数为 1） | 2 |
| 1024 | 2¹⁰ | 11 |
- 质数自身的质因数分解就是它本身，指数为 1，并且它总是恰好有 2 个约数：1 和它本身。这正是质数的定义性特征。
- 1 既不是质数也不是合数，没有质因数分解（它是空乘积）；本计算器要求输入大于或等于 2 的数。
- 对于非常大的数，试除法在计算上会变得很慢，因为它必须一直测试到该数平方根为止的所有候选质数——这也正是分解位数极多（成百上千位）的大数在计算上十分困难、并构成 RSA 加密安全基础的原因。
什么是质因数分解？
质因数分解是把一个整数拆解为若干个相乘等于该数的质数的过程。质数是大于 1、恰好只有两个正约数（1 和它本身）的整数（2、3、5、7、11、13……是最前面的几个质数）。例如，360 分解为 2³ × 3² × 5，也就是 360 = 2×2×2×3×3×5。
算术基本定理是数论的基石性结论之一，它保证了任何大于 1 的整数都有且仅有一种质因数分解方式（不考虑因数书写的先后顺序）。正是这种唯一性，使得质因数分解成为一个定义明确、结果可靠的运算，而不是众多同样有效的答案之一。
质因数分解是数学和计算机科学许多核心领域的基础：它被用来求数的最大公约数和最小公倍数、确定一个数的所有约数、化简分数和根式；对于非常大的数而言，质因数分解在计算上的困难性正是 RSA 公钥加密的数学基础——该体制依赖于一个事实：把一个大数分解为因数，远比把这些因数相乘困难得多。
如何使用本质因数分解计算器
- 输入一个大于或等于 2 的整数（最大到 1 万亿）。
- 计算器按照标准的试除法，反复用可能的最小质因数去除该数，直到只剩下 1 为止。
- 查看以指数形式给出的质因数分解结果（例如 2³ × 3² × 5），每个指数表示该质数在乘积中出现的次数。
- 查看该数正约数的总个数，以及所有这些约数之和——两者都直接由质因数分解推导得出。
质因数分解、约数个数与约数之和的计算方法
试除法从 2 开始依次测试候选质数，把该数尽可能多次地除以每个质数，然后再换下一个候选质数，以此求出质因数分解。举例说明：360 ÷ 2 = 180，÷2 = 90，÷2 = 45（不再能被 2 整除，所以 2 出现 3 次）；45 ÷ 3 = 15，÷3 = 5（不再能被 3 整除，所以 3 出现 2 次）；5 ÷ 5 = 1（5 出现 1 次）。结果：360 = 2³ × 3² × 5。
一旦知道质因数分解 n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ，正约数的总个数（包括 1 和 n 本身）就可以通过把每个指数加 1 后相乘求得：(e₁+1) × (e₂+1) × ... × (eₖ+1)。以 360 = 2³ × 3² × 5¹ 为例：(3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24 个约数。
所有约数之和可以用具有可乘性的约数和公式求得：对分解式中的每个质数幂 p^e，它的贡献是 (p^(e+1) − 1) ÷ (p − 1)——即等比级数 1 + p + p² + ... + p^e 的和——再把所有质因数的贡献相乘。以 360 为例：2³ 这一项贡献 (2⁴−1)/(2−1) = 15，3² 这一项贡献 (3³−1)/(3−1) = 13，5¹ 这一项贡献 (5²−1)/(5−1) = 6；三者相乘 15 × 13 × 6 = 1170，即 360 的全部 24 个约数之和。
常见错误
- 分解还没到 1 就提前停止——每找到一个因数，都必须把它除尽（而不是只除一次），才能换下一个候选质数。
- 把 1 当作质数——按照现代数学惯例，1 既不是质数也不是合数，如果把它算进分解式，就会破坏算术基本定理所保证的唯一性。
- 忘记指数（而不只是质数本身）对统计约数个数很重要——约数个数公式对每个质数使用的是（指数 + 1），而不是仅仅统计不同质数的个数。
- 以为每个大数都有较小的质因数——许多大数（尤其是两个大质数的乘积）根本没有任何较小的因数，而这正是它们能被用于密码学应用的关键特性。
常见问题
如何求一个数的质因数分解？
反复用能整除该数的最小质数去除它，用同一个质数一直除到不能再整除为止，再换下一个质数，如此重复直到商为 1。以 360 为例：先用 2 除三次（360→180→90→45），再用 3 除两次（45→15→5），再用 5 除一次（5→1），得到 360 = 2³ × 3² × 5。
一个数有多少个约数？
把质因数分解中每个指数加 1，再把结果相乘。以 360 = 2³ × 3² × 5¹ 为例，约数个数为 (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24。这统计的是全部正约数，包括 1 和该数本身。
什么是算术基本定理？
算术基本定理指出，任何大于 1 的整数都可以写成质数的乘积，且除了质数排列的先后顺序不同外，这种写法是唯一的。正是这种唯一性，使质因数分解成为一个定义明确的运算，而不是若干同样有效答案中的一个，它也是数论许多结论的基础。
1 是质数吗？
不是。按照现代数学惯例，1 既不是质数也不是合数。质数的定义是恰好有两个不同的正约数（1 和它本身）；而 1 只有一个正约数（它本身），不满足这一定义。把 1 排除在质数之外，也是算术基本定理成立所必需的，否则一个数就可以「分解」出任意多个多余的 1 作为因数。
为什么质因数分解对加密很重要？
现代 RSA 公钥加密依赖这样一个事实：把两个大质数相乘在计算上很容易，但用目前已知的经典算法把它们的大乘积重新分解回原来的质数，在计算上却非常困难。正是这种「相乘容易、分解困难」的不对称性，使得公钥（也就是那个乘积）可以公开分享，而私钥（也就是那两个质因数）在质数足够大时能够保密，实际上在合理时间内无法被反推出来。
如何求一个数所有约数之和？
利用质因数分解 n = p₁^e₁ × p₂^e₂ × ...，对每个质因数计算 (pᵢ^(eᵢ+1) − 1) ÷ (pᵢ − 1)，再把结果相乘。以 360 = 2³ × 3² × 5 为例：2³ 这一项给出 (2⁴−1)/(2−1)=15，3² 这一项给出 (3³−1)/(3−1)=13，5¹ 这一项给出 (5²−1)/(5−1)=6；三者相乘 15×13×6 = 1170，即 360 所有约数之和。
参考文献
- Rosen KH. Elementary Number Theory and Its Applications. 6th ed. Pearson, 2010. (Fundamental theorem of arithmetic, divisor functions.)
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. 6th ed. Oxford University Press, 2008.
- Rivest RL, Shamir A, Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 1978; 21(2): 120–126. (RSA and the factoring problem.)