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

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

---

不断循环，计算 n 的质因数之和 s。如果 s=n 说明无法再继续减小 n 了，返回 n；否则更新 n 为 s，继续循环。

[sol1-Python3]

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

[sol1-Go]

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
	}
}

复杂度分析

• 时间复杂度：O(\sqrt n)。最坏情况下每次循环 n 更新为 2+n/2，近似看成是 n 减半，那么时间复杂度为 O\left(\sqrt n + \sqrt\dfrac{n}{2} + \sqrt\dfrac{n}{4} + \cdots \right)=O\left(\sqrt n\cdot \left(1 + \sqrt\dfrac{1/2} + \sqrt\dfrac{1/4} + \cdots\right)\right) = O(\sqrt n)。
• 空间复杂度：O(1)，仅用到若干变量。