题目链接

Leetcode.2507 使用质因数之和替换后可以取到的最小值 Rating ： 1500

题目描述

给你一个正整数 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<=10^5$

解法：质因数分解

对 $n$ 进行质因数分解，把 $n$ 替换为 $n$的质因数之和。

我们用 $pre$ 记录前一个质因数之和。

当 $n$ 为最小质因数之和时，再进行同样的上述操作，值是不会改变的。所以当 $pre=n$时，说明此时的 $n$ 就是最小质因数之和。

时间复杂度： $O(\sqrt{n})$

C++代码：

class Solution {
public:int smallestValue(int n) {int pre = 0;while(pre != n){int sum = 0;pre = n;for(int x = 2;x <= n / x;x++){while(n % x == 0){sum += x;n /= x;}}if(n > 1) sum += n;n = sum;}return n;}
};