C+++分治算法------ 整数因子分解

清疚 2024-03-22 11:31 43阅读 0赞

代码：

当n=12时，整数因子分解的递归过程

运行结果：

--------------------

## C+++分治算法------ 整数因子分解 ##

![ba395289ed894452b6e1e315276f1ac5.png][]

### 代码： ###

#include <iostream>
    using namespace std;
    
    int total;
    
    void solve(int n) {
        if (n == 1)
            total++;
        else {
            for (int i = 2; i <= n; i++) {
                if (n % i == 0)
                    solve(n / i);
            }
        }
    }
    
    int main() {
        int n;
        while (cin >> n && n != 0) {
            total = 0; // 每次循环前将total清零
            solve(n);
            cout << total << endl;
        }
        return 0;
    }

> #### **当****n=12****时****，整数因子分解的递归过程** ####

![80dd5286ca35477fb85e4ceb4d2963e6.png][]

> 这段代码实现了计算给定正整数n的不同质因数分解式个数的功能，基于递归方法实现。其原理是枚举n的所有因子并进行递归调用，直到达到质数为止。
> 
> 具体而言，for循环从2开始枚举n的因子i，如果i是n的因子，则将n/i作为新的待分解数，继续递归调用solve函数；否则增加i的值，继续枚举。
> 
> 当n=1时，表明分解结束，此时total加1，表示得到了一种不同的质因数分解式。当n是质数时，总的分解式个数为1。
> 
> 需要注意的是，在递归调用solve函数时，每次都使用n/i作为新的待分解数而非未除尽的部分，这是因为对于任意正整数n和其因子i，n/i一定是另一个因子，两者是互补的。因此，只需要对n/i进行递归，就可以遍历到所有的因子，无需考虑i除不尽的剩余部分。
> 
> 另外，为了避免重复计数，当在当前层找到了一个因子时，应当及时返回，不再继续枚举。因为继续枚举可能会得到相同的分解式，导致重复计数。
> 
> 综上，该代码正确实现了计算不同质因数分解式个数的功能。

### 运行结果： ###

![31c00f8a27bb470d90e2d68f9f28f775.png][]

[ba395289ed894452b6e1e315276f1ac5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/3f12f74ad8ae43849916886ce8bcd150.png
[80dd5286ca35477fb85e4ceb4d2963e6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/b7ccb3888e5e48aa9d5cbce8887c15a3.png
[31c00f8a27bb470d90e2d68f9f28f775.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/401f8e4918d5430c8131131758a57610.png