下载掌阅APP，畅读海量书库
立即打开
正整数 S 可表示为若干个正整数的乘积，即 S = s 1 × s 2 ×…× s n ，其中各个因子构成一个递增序列，即 s 1 ≤ s 2 ≤ s 3 ≤…≤ s n ，称之为 S 的因数分解。一个正整数 S 的分解中，各因子间是无序的，如12=2×2×3、12=2×3×2和12=3×2×2对应的是同一个分解。因此，限定 S = s 1 × s 2 ×…× s n 中 s 1 ≤ s 2 ≤ s 3 ≤…≤ s n 以确保不会由于因子对称等原因导致重复解。每一种 S = s 1 × s 2 ×…× s n 称为 S 的一个分解，需要注意的是 s = S 也是一种分解。例如4、8、12和24的分解数分别为2、3、4和7，分解过程如下。
以24为例，对24的各个分解进行整理和重新排列，可以得出以下规律。
（1）1和24自身构成24的第一组分解，对应①。
（2）②、③、④和⑤构成2和12对应的第二组分解。
（3）3和8构成24的第三组分解，对应⑥。
（4）4和6构成24的第四组分解，对应⑦。
从整体上看，各组分解的首个因子呈递增趋势，这就意味着各组分解的第二因子必定呈递减趋势。从局部看，②、③、④和⑤中，③、④和⑤分别对应12的一组分解，其分解方法与24的分解方法相同。进一步，③和④中，④是③中第二个因子6的一组分解。各组分解中，第一因子有上限值
S
/2，更进一步可限定为
。各子分解中，第二因子不小于第一因子。
从上述分析可以得出，24的各组分解中存在子分解，子分解与原分解的规律相同，规模减小，具有典型的递归特征。因此，可以使用递归来解决因数分解问题。
令 S i = S /（ s 1 × s 2 ×…× s i ），对 S 进行分解时，其分解过程如下。
（1） S 自身算一种分解。
（2）剩余分解可以通过
范围内的每一个整数
k
进行试除。
①若 s i = k 为 S 的因子，则寻找到1个新的分解 s 1 × s 2 ×…× s i × S i 。
②同时还应该注意到， S i 仍有可能含最小因子不小于 s i = k 的分解，需要对 S i 从 s i = k 开始继续分解。
图3-3给出了正整数4、8、12和24从2开始进行因数分解的示意图。
图3-3 4、8、12和24的从2开始进行因数分解的示意图
以24为例，其因数分解过程如下。
（1）24自身是一种分解，因此获得第1种分解24=24。
取
k
=2，3，4（因为
）分别试除进行分解，递增试除保证了各个因子间是递增的，而且不会出现重复分解。
（2）当 s 1 = k =2时，4种分解如下。
① S 1 = S / s 1 =24/2=12，获得第2种分解 S = s 1 × S 1 ，即24=2×12。
② S 1 可进一步进行分解，取 s 2 = k =2， S 2 = S /（ s 1 × s 2 ）=24/（2×2）=6，获得第3种分解 S = s 1 × s 2 × S 2 ，即24=2×2×6； S 2 可进一步进行分解，取 s 3 = k =2， S 3 = S /（ s 1 × s 2 × s 3 ）=3，获得第4种分解 S = s 1 × s 2 × s 3 × S 3 ，即24=2×2×2×3。
③ S 1 可进一步进行分解，取 s 2 = k +1=3， S 2 = S /（ s 1 × s 2 ）=4，获得第5种分解 S = s 1 × s 2 × S 2 ，即24=2×3×4。
（3）当 s 1 = k =3时， S 1 = S / s 1 =24/3=8，获得第6种分解 S = s 1 × S 1 ，即24=3×8。
（4）当 s 1 = k =4时， S 1 = S / s 1 =24/4=6，获得第7种分解 S = s 1 × S 1 ，即24=4×6。
第2种分解方法主要是通过对问题的分析，获得子问题的表述，根据递归表达式来进行求解。3.3.1节通过试除法，利用
之间的因子获取某个分解。也可以从
S
出发，以因子递减方式逐步尝试对
S
及其因子进行分解，最终基于解的加法原理获得
S
的各个分解。
S
的分解因数问题
N
（
S
，
m
）的递归表达式如式（3.3）所示。
其中，
m
|
S
表示
S
能被
m
整除，
表示
S
不能被
m
整除。
get_factor_numbers1（）函数使用因子递增方式进行因数分解。函数有两个参数，n是待分解的数值，m是分解的起始值（一般从2开始，即m的初值为2）。函数在进行因数分解时，①将因数为自身的情况计入统计过程；②当重复分解至1时，分解过程结束；③未分解至1时，用循环变量i从2到
逐个遍历进行试除，若试除成功则将n/i从i开始进一步分解。
实现代码如下。
get_factor_numbers2（）函数使用子问题分解方式进行因数分解。函数有2个参数，n是待分解的数值，m是分解的起始值（代表要分解的（疑似）最大因子，一般从n开始，逐渐递减至1）。函数在进行因数分解时，若被分解的数为1时，只有一种分解方式；若最大因子为1时，则返回0；若m为n的因子，则进行递归分解并统计解的总和；若m不为n的因子，则从m-1开始继续尝试新的分解过程。
测试数据及运行结果如下。
当输入两个测试数据：12和24时，12有4种分解方式，24有7种分解方式，运行结果如下。
