/**
1. dp: 本题最后一定是由某个状态的一次copy,多次paste而来, 所以符合"最优子结构"和"无后效性", 可以用动态规划来做
1.1 状态定义: f[i] 获取 i个的最小操作数
1.2 状态计算: 从最后一个位置i分析, 因为可以paste多次, 所以可以从i的任意约数j扩展而来 -> f[i] = MIN(f[j] + i/j)
1.3 边界: f[~] = INF, f[1] = 0
1.4 剪枝: 
    1.4.1 只需要扩展n的约数即可
    1.4.2 约数j 最大的情况下为 sqrt(i)


2. 数论: 本题最后一定是由某个状态的一次copy,多次paste而来, 即 y -> px, 可以按p讨论
2.1 如果p是一个质数, 无法分解讨论
2.2 如果p是一个合数, 那么可以尝试拆分成2个更小的数p=i*j , y -> ix -> ijx , 分解前 i*j 步, 分解后 i + j 步
    2.2.1 根据加和与乘积的性质, 当 i,j = 2 时 i+j == i*j
                              当 i 或 j > 2 时, i + j < i * j
                              当 i 或 j < 2 时, i + j > i * j
    2.2.2 本题 i > 1 , j > 1 所以 i + j <= i *j , 故将合数拆分后结果集可能更小, 所以最终结果必定为n 的质因数分解的和
*/

class Solution {
    public int minSteps(int n) {
        // return dp(n);
        return math(n);
    }

    public int math(int n){
        int res = 0;
        for (int i = 2 ; n > 1 ; i++){
            while (n % i == 0){
                res += i;
                n /= i;
            }
        }
        return res;
    }

    public int dp(int n){
        int[] f = new int[n+1];
        Arrays.fill(f, Integer.MAX_VALUE);
        f[1] = 0;
        for (int i= 2 ; i <= n ; i++){
            if (n % i != 0) continue;
            for (int j = 1; j*j <= i ; j++){
                if (i % j != 0) continue;
                f[i] = Math.min(f[i], f[j] + i/j);
                f[i] = Math.min(f[i], f[i/j] + j);
            }
        }
        return f[n];
    }
}