https://leetcode.cn/problems/smallest-value-after-replacing-with-sum-of-prime-factors/description/
给你一个正整数 n 。
请你将 n 的值替换为 n 的 质因数 之和，重复这一过程。
注意，如果 n 能够被某个质因数多次整除，则在求和时，应当包含这个质因数同样次数。
返回 n 可以取到的最小值。
示例 1：
输入：n = 15
输出：5
解释：最开始，n = 15 。
15 = 3 * 5 ，所以 n 替换为 3 + 5 = 8 。
8 = 2 * 2 * 2 ，所以 n 替换为 2 + 2 + 2 = 6 。
6 = 2 * 3 ，所以 n 替换为 2 + 3 = 5 。
5 是 n 可以取到的最小值。
示例 2：
输入：n = 3
输出：3
解释：最开始，n = 3 。
3 是 n 可以取到的最小值。
提示：
2 <= n <= 10^5
分解质因数的模版题
class Solution {
public:
int primes[100010][2];
int idx = 0;
void splitPrime(int n) {
memset(primes, 0, sizeof primes);
idx = 0;
bool vis[100010]; memset(vis, 0, sizeof vis);
int cp = n;
//每个数标记一次 复杂度O(n)
for (int i = 2; i <= n ; i++) {
if (vis[i] == 1) continue;
while (cp % i == 0) {
cp /= i;
primes[idx][0] = i;
primes[idx][1]++;
}
if (primes[idx][1] > 0) idx++;
for (int j = i + i; j <= n; j += i) {
vis[j] = 1;
}
}
}
int smallestValue(int n) {
while (1) {
//循环分解质因数 然后使用数组记录 获取所有质因数之和
int sum = 0;
splitPrime(n);
for (int i = 0; i < idx; i++) {
sum += primes[i][1]*primes[i][0];
}
if (sum == n) break;
n = sum;
}
return n;
}
};
但是这样太过冗余 最后优化到 复杂度O(sqrt(n))
class Solution {
public:
int smallestValue(int n) {
int pre = 0;
while (pre != n) {
pre = n; int sum = 0;
for (int i = 2; i <= n / i; i++) {
//只需要遍历到 sqrt(n)即可
while (n % i == 0) {
//第一次能整除n的数 一定是质数 比如2循环从n中整除后
// 4 6 8 10 就不可能整除没有2因子的n 了
n = n / i;
sum += i;
}
}
//最后n可能变成1 可能变成一个没有之前因子的一个质数
//如果是质数 则也要加入质数和变量中
if (n > 1) sum += n;
n = sum;
}
return n;
}
};