难度: Medium
给你一个正整数 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运行时间: 28 ms
内存: 16.1 MB
class Solution:
def smallestValue(self, n: int) -> int:
# a1 * a2 * a3 = n
while 1:
i = 2
j = 0
s = n
while i * i <= n:
while n % i == 0:
j += i
n = n//i
i += 1
if n > 1:
j += n
if j == s:
return j
n = j
#9-16行是质因数分解方法，只需要根号n的时间
#证明： 1.假设已经得到(a1, a2, .., ak)为因数
#那么它们都是质因数， 如果ak是合数，且之前的都是质因数，那么其必然能够质因数分解，则这些质因数是在{a1,..ak-1}之间的
#但是，这些质因数在之前都分解完了。这导致矛盾
#2.假设10-14得到(a1,a2,...,am)（由1，它们都是质因数），剩下n是质因数或1。
#如果不是，那么n包含至少两个不小于am的质因数，那么其中一个必然会被分解出来（矛盾）
#因此得到的质因数列为(a1,a2,...,am, n)（如果n不等1）
这个题解的思路是通过不断重复替换整数n为其质因数之和，直到n不能再变小。在每次迭代中，算法首先尝试从最小的质因数2开始，逐步检查每个数是否是n的质因数，并将其累加到变量j中。如果在检查到i * i > n时仍有剩余的n大于1，这意味着n本身是一个质因数，此时将其加到j中。如果新的j与原始的n相同，则说明n已经是其质因数之和的最小值，算法结束返回j。
时间复杂度: O(n * sqrt(n))
空间复杂度: O(1)
class Solution:
def smallestValue(self, n: int) -> int:
# 重复替换n为其质因数之和，直到无法进一步减小
while True:
i = 2
j = 0
s = n
# 质因数分解n
while i * i <= n:
while n % i == 0:
j += i
n = n // i
i += 1
# 检查是否有大于sqrt(n)的质因数
if n > 1:
j += n
# 如果n不再变化，返回结果
if j == s:
return j
# 准备下一轮迭代
n = j
算法通过质因数分解确保每次迭代的n值都仅包含n的质因数。在循环中，算法从2开始递增，检查每个数是否能整除n。如果能，则该数是n的质因数，并且会不断除以该因数直至不能整除为止。这样，算法确保加入到j中的每个因数都是n的质因数，不存在非质因数的组合。
这一逻辑通常是有效的，因为每次迭代的目的是通过质因数之和减小n的值。如果在某次迭代后n的值没有变化，表明n已经是其所有质因数的和，且无法通过当前的方法进一步简化。因此，算法停止是合理的。在此算法框架下，不会出现因特定输入导致的提前终止。
从2开始检查是因为2是最小的质因数，并且任何合数都至少有一个不大于其平方根的质因数。从2开始可以确保按照从小到大的顺序识别并分解出所有质因数。如果从更高的数开始，可能会错过较小的质因数，导致算法无法正确分解n。从2开始虽然可能会略增加迭代次数，但这保证了算法的正确性和全面性。
该假设总是成立的。当i * i > n时，如果n大于1，则n不能被任何小于或等于其平方根的数整除。因此，n必须是质数，因为质数的定义是只能被1和自身整除。所以这种情况下，将n加入到j是正确的。