Skip to content

2507. Smallest Value After Replacing With Sum of Prime Factors 👍

  • Time: $O(\log n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int smallestValue(int n) {
    int primeSum = getPrimeSum(n);
    while (n != primeSum) {
      n = primeSum;
      primeSum = getPrimeSum(n);
    }
    return n;
  }

 private:
  int getPrimeSum(int n) {
    int primeSum = 0;
    for (int i = 2; i <= n; ++i)
      while (n % i == 0) {
        n /= i;
        primeSum += i;
      }
    return primeSum;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int smallestValue(int n) {
    int primeSum = getPrimeSum(n);
    while (n != primeSum) {
      n = primeSum;
      primeSum = getPrimeSum(n);
    }
    return n;
  }

  private int getPrimeSum(int n) {
    int primeSum = 0;
    for (int i = 2; i <= n; ++i)
      while (n % i == 0) {
        n /= i;
        primeSum += i;
      }
    return primeSum;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def smallestValue(self, n: int) -> int:
    def getPrimeSum(n: int) -> int:
      primeSum = 0
      for i in range(2, n + 1):
        while n % i == 0:
          n //= i
          primeSum += i
      return primeSum

    primeSum = getPrimeSum(n)
    while n != primeSum:
      n = primeSum
      primeSum = getPrimeSum(n)
    return n