P202: Determine the prime factors of a given positive integer

质因数分解。

在数学中，整数分解又称质因数分解（prime factorization），是将一个正整数写成几个因数皫乘积。例如，给出45这个数，它可以分解成$3^2*5$。根据算术基本定理，这样的分解结果应该是独一无二的。这个问题在代数学、密码学、计算复杂性理论和量子计算机等领域中有重要意义。^{wiki-integer-factorization}

照例先写测试用例：

试除法

试除法是整数分解算法中最简单和最容易理解的算法。首次出现于义大利数学家斐波那契出版于1202年的着作。

给定一个合数n（这里，n是待分解的正整数），试除法看成是用小于等于 ${\displaystyle {\sqrt {n}}}$的每个质数去试除待分解的整数。如果找到一个数能够整除除尽，这个数就是待分解整数的因子。试除法一定能够找到n的因子。因为它检查n的所有可能的因子，所以如果这个算法「失败」，也就证明了n是个质数。试除法可以从几条途径来完善。例如，n的末位数不是0或者5，那么算法中就可以跳过末位数是5的因子。如果末位数是2，检查偶数因子就可以了。

某种意义上说，试除法是个效率非常低的算法，如果从2开始，一直算到 ${\displaystyle {\sqrt {n}}}$需要 ${\displaystyle \pi ({\sqrt {n}})}$次试除，这里$\pi(x)$是小于x的质数的个数。这是不包括质数测试的。如果稍做变通——还是不包括质数测试——用小于 ${\displaystyle {\sqrt {n}}}$的奇数去简单的试除，则需要 ${\displaystyle {\sqrt {n} \over 2}}$次。这意味着，如果n有大小接近的质因子（例如公钥密码学中用到的），试除法是不太可能实行的。但是，当n有至少一个小因子，试除法可以很快找到这个小因子。值得注意的是，对于随机的n，2是其因子的机率是50％，3是33％，等等，88％的正整数有小于100的因子，91％的正整数有小于1000的因子。^{wiki-trial-division}

我们就用「效率非常低」的「试除法」。用一个质数去除，若能整除（余数为0），则该质数为其中一个质因数，继续用该质数去除商数；若不能整除（余数不为0），则该质数不为其中一个质因数，尝试用下一个质数去除；直至商数是质数（为质数的商数为最后一个质因数。

举个例子，给定数字315：

1. 先用最小的质数2去除，发现不能整除 $315 \mod 2 = 1$
2. 再用2后一个质数3去除，发现315能被3整除且商为105，所以3是其质因数之一
3. 再用3除商数105，发现能整除且商为35，所有其质因数序列中有两个3
4. 再用3除商数35，发现不能整除，则用下一个质数5去除，发现能除且商为7，所以5是其质因数之一
5. 商数7是质数，其是最后一个质因素。最终得到质因素列表[3, 3, 5, 7]

$$\begin{align*} 315 &= 2^0 \times 315 \tag{1} \\ &= 2^0 \times 3^1 \times 105 \tag{2} \\ &= 2^0 \times 3^2 \times 35 \tag{3} \\ &= 2^0 \times 3^2 \times 5^1 \times 7 \tag{4} \\ & = 2^0 \times 3^2 \times 5^1 \times 7^1 \tag{5} \end{align*}$$

代码实现：

为实现以上算法，我们需要两个辅助函数：「判断是否为质数」和「下一个质数」。「判断是否为质数」可以重用P201中实现的is_prime。而「下一个质数」则需要现埸实现。根据伯特兰-切比雪夫定理，给定整数$n$，遍历$n$至$2n$之间的整数，一定能找到一个质数。

伯特兰-切比雪夫定理说明：若整数$n>3$，则至少存在一个质数$p$，符合 $n<p<2n-2$。另一个稍弱说法是：对于所有大于1的整数$n$，存在一个质数$p$，符合$n<p<2n$。1845年约瑟．伯特兰提出这个猜想。伯特兰检查了2至$3\times10^6$之间的所有数。1850年切比雪夫证明了这个猜想。拉马努金给出较简单的证明，而保罗．艾狄胥则借二项式人竹女戈火数给出了另一个简单的证明。^{wiki-Bertrand}

「下一个质数」代码实现：

参考文献

^{wiki-trial-division}. https://zh.wikipedia.org/wiki/试除法 ↩