Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2507.html
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 dividesn
.
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
-
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; } } };
-
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
-
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 } }