【leetcode】只（质）因树之和

题目链接: 2507. 使用质因数之和替换后可以取到的最小值 - 力扣（Leetcode）

题面

给你一个正整数 n 。

请你将 n 的值替换为 n 的 质因数 之和，重复这一过程。

• 注意，如果 n 能够被某个质因数多次整除，则在求和时，应当包含这个质因数同样次数。

返回 n 可以取到的最小值。

示例 1：

输入：n = 15
输出：5
解释：最开始，n = 15 。
15 = 3 * 5 ，所以 n 替换为 3 + 5 = 8 。
8 = 2 * 2 * 2 ，所以 n 替换为 2 + 2 + 2 = 6 。
6 = 2 * 3 ，所以 n 替换为 2 + 3 = 5 。
5 是 n 可以取到的最小值。

示例 2：

输入：n = 3
输出：3
解释：最开始，n = 3 。
3 是 n 可以取到的最小值。

提示：

• 2 <= n <= 1e5

解题思路

一个数一定可以被分解为一个或者多个质数，这些质数被称为这个数的质因数，所以要解决这个题的问题就化解为求一个树的质因数了，因此我们想到：因为本题的数据量不大，仅有 1e5，我们可以把所有的质数都求出来，再利用求出的表计算所有的质因数。但是事实上，因为这种方法求出了很多可能根本不会使用到的值，浪费了时间，因此我们可以进行一下优化。

ACCode

class Solution {
public:
    int divide(int n) {
        int ans = 0;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                int k = 0;
                while (n % i == 0) {
                    n /= i;
                    k++;
                }
                ans += (i * k); // 拥有 k 个等于 i 的质因子
            }
        }
        if (n > 1) {
            ans += n;
        }

        return ans;
    }
    
    int smallestValue(int n) {
    
        int x = divide(n);
        while (x != n) {
            n = x;
            x = divide(n);
        }
        
        return x;
    }
};