C++ 代码

本质是分解质因数
以 12 为例
12 = 2 * 2 * 3
比如 1 -> 3 -> 6 -> 12
1 -> 3 复制1次，粘贴（3-1 = 2）次，一共3次
3 -> 6 复制1次，粘贴（2-1 = 1）次，一共2次
6 -> 12 复制1次，粘贴（2-1 = 1）次，一共2次
总共 3 + 2 + 2 = 7 次
操作次序可以调整，结果不变

只有按照 “因数” 进行操作才能得到最终结果

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e6 + 10;

int n, ans;
int cnt, prim[100000];
bool is_prim[N];

void Euler()
{
    cnt = 0;
    memset(is_prim, 0, sizeof is_prim);

    for (int i=2; i<N; i++) {
        if (!is_prim[i]) prim[++cnt] = i;
        for (int j=1; j<=cnt && i*prim[j] < N; j++) {
            is_prim[i*prim[j]] = true;
            if (i % prim[j] == 0) break;
        }
    }

    // cout << cnt << endl;
    // for (int i=1; i<=100; i++) cout << prim[i] << '\n';

}


int main()
{
    Euler();
    cin >> n;

    while (n > 1) {
        for (int i=1; i<=cnt; i++) {
            while (n % prim[i] == 0) {
                ans += prim[i];
                n /= prim[i];
            }
            if (n == 1) break;
        }
    }

    cout << ans << '\n';
    return 0;
}