[LeetCode] Smallest Value After Replacing With Sum of Prime Factors

2507. Smallest Value After Replacing With Sum of Prime Factors

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int smallestValue(int n) {
while(true) {
int now = 0;
int origin = n;
for(int i = 2; i * i <= n; i++) {
if(n % i) continue;
while(n % i == 0) {
n /= i;
now += i;
}
}
if(n != 1) {
now += n;
}
if(origin > now) n = now;
else return now;
}
return -1;
}
};

Author: Song Hayoung
Link: https://songhayoung.github.io/2022/12/18/PS/LeetCode/smallest-value-after-replacing-with-sum-of-prime-factors/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.