class Solution {
public:
int smallestValue(int n) {
}
};
2507. 使用质因数之和替换后可以取到的最小值
给你一个正整数 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 <= 105原站题解
java 解法, 执行用时: 2 ms, 内存消耗: 38.5 MB, 提交时间: 2022-12-20 09:54:29
class Solution {
public int smallestValue(int n) {
int ans = 0, tmp = n;
for (int i = 2; tmp > 1; i++) {
while (tmp % i == 0) {
tmp /= i;
ans += i;
}
}
return ans == n ? n : smallestValue(ans);
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 1.8 MB, 提交时间: 2022-12-20 09:53:39
func smallestValue(n int) int {
for {
x, s := n, 0
for i := 2; i*i <= x; i++ {
for ; x%i == 0; x /= i {
s += i
}
}
if x > 1 {
s += x
}
if s == n {
return n
}
n = s
}
}
python3 解法, 执行用时: 40 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-20 09:53:26
'''
不断循环，计算n的质因数之和s。如果s=n说明无法再继续减小n了，返回n；否则更新n为s，继续循环。
'''
class Solution:
def smallestValue(self, n: int) -> int:
while True:
x, s, i = n, 0, 2
while i * i <= x:
while x % i == 0:
s += i
x //= i
i += 1
if x > 1: s += x
if s == n: return n
n = s