Question

2507. Smallest Value After Replacing With Sum of Prime Factors

中文文档

Description

You are given a positive integer n.

Continuously replace n with the sum of its prime factors.

• Note that if a prime factor divides n multiple times, it should be included in the sum as many times as it divides n.

Return _the smallest value _n_ will take on._

 

Example 1:

Input: n = 15
Output: 5
Explanation: Initially, n = 15.
15 = 3 * 5, so replace n with 3 + 5 = 8.
8 = 2 * 2 * 2, so replace n with 2 + 2 + 2 = 6.
6 = 2 * 3, so replace n with 2 + 3 = 5.
5 is the smallest value n will take on.

Example 2:

Input: n = 3
Output: 3
Explanation: Initially, n = 3.
3 is the smallest value n will take on.

 

Constraints:

• 2 <= n <= 105

Solutions

Solution 1

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