友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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
nmultiple 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
思路分析
看答案有些懵逼，没看到计算质数的过程。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Copy https://leetcode.cn/problems/smallest-value-after-replacing-with-sum-of-prime-factors/solutions/2024532/bao-li-by-endlesscheng-xh0b/
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-25 15:22:24
*/
public int smallestValue(int n) {
int result = 0;
int cur = n;
for (int i = 2; i * i <= cur; i++) {
while (cur % i == 0) {
result += i;
cur /= i;
}
}
if (cur > 1) {
result += cur;
}
return result == n ? result : smallestValue(result);
}