上一篇文章我们用直到循环的算法，给出了整数质因子分解的程序，本篇我们使用递归的算法来解决质因数分解问题。

（一）算法分析

（1）先要会建一个判断一个数是否质数的程序。可有多种方法，我们就用最常规的穷举方法，先给”标志变量”赋值1，如果中间有数整除的，立即停止，给”标志变量”赋值0，如果一直都没有赋值0，”标志变量”值是1，就意味着这个数就是质数。

（2）利用前面建立的程序，建立递归程序。

若N≤3，则N的分解直接给出，如果N>3,则对N进行判断，即对k从2开始到N的平方根为止，逐一去除N，如果某个k整除N了，停止判断，记住此时的k值，即传给中转，给”标志变量”赋值0，如果一直都没有赋值0，”标志变量”值是1，就意味着这个数就是质数。

如果”标志变量”=1，则将此时的N值和乘号加入“乘积”，否则就对“中转”和“N/中转”调用递归程序。

（二）编程实现

1.分解质因数的递归子程序：

2.主程序，根据用户输入的待分解数，对回答调用递归子程序即可：

3.例如，给出728345570这个数，它可以分解成2×5×173×5×421009。

（三）表现形式是否可以改进成如下方幂形式呢？

看来需要一个列表把分解的质因数先全部存放在列表“质因数表”中，然后逐一取出组成字符串，其间要把相同的质数个数做幂指数表现。

2.主程序也做相应改动：