力扣 650. 只有两个键的键盘

题目来源：https://leetcode-cn.com/problems/2-keys-keyboard/

大致题意：
给定一个字符个数 n，假定初始时只有一个字符。每次进行的操作只能有两种：

1. 复制所有元素
2. 粘贴刚刚复制的内容

求出将字符复制成 n 个需要的操作次数

思路

• 如果当前数 num 是偶数，那么它肯定是由 num/2 复制过来的
• 如果当前数 num 是奇数，则它要么是由 num 的某个非 1 因数（即 num 不是质数）复制过来的，要么就是从 1 开始一下一下粘贴过来的

对应的次数：

• 对于是偶数的情况，那么需要的操作次数就为：到达 num/2 的次数 + 2，+ 2 是一次复制加一次粘贴
• 对于奇数的情况，如果它不是质数，那么需要的操作次数就是：到达 num 的最大因数的次数 + num / 最大因数，+ num / 最大因数 是从最大因数复制再粘贴到 num 需要的次数；若它是质数，显然只能从 1 一下一下的粘贴 num - 1 次，再加上一次复制，就是 num 次

代码：

public int minSteps(int n) {
        if (n == 1)
            return 0;
        // n 为偶数的情况
        if (n % 2 == 0)
            return minSteps(n / 2) + 2;
        // n 为奇数的情况
        else {
            for (int i = n / 2; i > 1; i--) {
                int factor = n / i;
                // 如果 i 是 n 的因数
                if (factor * i == n) {
                    // 返回构成 i 的次数，加上从 i 复制到 n 的次数
                    return minSteps(i) + factor;
                }
            }
            // n 的最大因数是 1, n 为质数
            return n;
        }
    }