Question

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

English Version

题目描述

给你一个正整数 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

解法

方法一：暴力模拟

根据题意，我们可以得到一个质因数分解的过程，即将一个数不断地分解为质因数，分解不能分解。过程中将每次分解的质因数相加，递归或者迭代地进行即可。

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

class Solution:
  def smallestValue(self, n: int) -> int:
    while 1:
      t, s, i = n, 0, 2
      while i <= n // i:
        while n % i == 0:
          n //= i
          s += i
        i += 1
      if n > 1:
        s += n
      if s == t:
        return t
      n = s

class Solution {
  public int smallestValue(int n) {
    while (true) {
      int t = n, s = 0;
      for (int i = 2; i <= n / i; ++i) {
        while (n % i == 0) {
          s += i;
          n /= i;
        }
      }
      if (n > 1) {
        s += n;
      }
      if (s == t) {
        return s;
      }
      n = s;
    }
  }
}

class Solution {
public:
  int smallestValue(int n) {
    while (1) {
      int t = n, s = 0;
      for (int i = 2; i <= n / i; ++i) {
        while (n % i == 0) {
          s += i;
          n /= i;
        }
      }
      if (n > 1) s += n;
      if (s == t) return s;
      n = s;
    }
  }
};

func smallestValue(n int) int {
  for {
    t, s := n, 0
    for i := 2; i <= n/i; i++ {
      for n%i == 0 {
        s += i
        n /= i
      }
    }
    if n > 1 {
      s += n
    }
    if s == t {
      return s
    }
    n = s
  }
}