Medium

题目描述

给你一个正整数 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 的数字，找到每个数字整除 n 的最大次数。

解题思路

这道题要求我们不断将数字替换为其质因数之和，直到找到最小值。

核心思路：

  1. 质因数分解：对于给定的数字 n，找到所有质因数，包括重复的质因数
  2. 模拟过程：计算质因数之和，如果和与原数相同，说明原数就是质数，直接返回；否则继续对新的和进行处理
  3. 终止条件：当数字是质数时，质因数分解的和就是它本身，此时达到稳定状态

算法步骤：

  1. 编写质因数分解函数，从 2 开始试除，找到所有质因数
  2. 重复执行：计算当前数的质因数之和
  3. 如果新的和等于原数，说明原数是质数，返回结果
  4. 否则用新的和继续下一轮处理

优化要点：

  • 质因数分解时只需要检查到 √n，因为大于 √n 的因数最多只有一个
  • 每次替换后数字都会变小，所以算法会很快收敛
  • 当数字变为质数时，过程就会停止

代码实现

class Solution {
public:
    int smallestValue(int n) {
        while (true) {
            int sum = getPrimeFactorSum(n);
            if (sum == n) {
                return n;
            }
            n = sum;
        }
    }
    
private:
    int getPrimeFactorSum(int n) {
        int sum = 0;
        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                sum += i;
                n /= i;
            }
        }
        if (n > 1) {
            sum += n;
        }
        return sum;
    }
};

class Solution:
    def smallestValue(self, n: int) -> int:
        def get_prime_factor_sum(num):
            total = 0
            i = 2
            while i * i <= num:
                while num % i == 0:
                    total += i
                    num //= i
                i += 1
            if num > 1:
                total += num
            return total
        
        while True:
            prime_sum = get_prime_factor_sum(n)
            if prime_sum == n:
                return n
            n = prime_sum

public class Solution {
    public int SmallestValue(int n) {
        while (true) {
            int sum = GetPrimeFactorSum(n);
            if (sum == n) {
                return n;
            }
            n = sum;
        }
    }
    
    private int GetPrimeFactorSum(int n) {
        int sum = 0;
        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                sum += i;
                n /= i;
            }
        }
        if (n > 1) {
            sum += n;
        }
        return sum;
    }
}

var smallestValue = function(n) {
    function sumOfPrimeFactors(num) {
        let sum = 0;
        let factor = 2;
        
        while (factor * factor <= num) {
            while (num % factor === 0) {
                sum += factor;
                num /= factor;
            }
            factor++;
        }
        
        if (num > 1) {
            sum += num;
        }
        
        return sum;
    }
    
    while (true) {
        let sum = sumOfPrimeFactors(n);
        if (sum === n) {
            return n;
        }
        n = sum;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析结果
时间复杂度O(log n × √n)
空间复杂度O(1)

时间复杂度说明：

  • 质因数分解单次操作为 O(√n)
  • 由于每次替换后数字都会显著减小，最多需要 O(log n) 次迭代
  • 总时间复杂度为 O(log n × √n)

空间复杂度说明：

  • 只使用了常数级别的额外空间

相关题目