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:
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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
|
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) {
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;
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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;
}
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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
}
}
|
