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

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