算法篇8-LeetCode650. 只有两个键的键盘

一道有意思的题目

只有两个键的键盘

这题目自己思考了一下，还真的挺有意思的。首先，得知道如果输入的数n是一个素数，那么就必须得用n次操作才能完成，因为素数不能拆成任何数的乘积，所以只能一个一个复制粘贴。然后考虑的是合数，如果合数能拆成多个素数的乘积，那就是先复制粘贴一个素数，再对素数进行复制粘贴，就能得到合数了。所以，这道题目就变成了输入的n拆成素数乘积的形式，而操作的次数正好是拆成的素数的和。
代码如下：

public int minSteps(int n) {
        /**
         *
         * 功能描述: 最初在一个记事本上只有一个字符 'A'。你每次可以对这个记事本进行两种操作：
         *
         * Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
         * Paste (粘贴) : 你可以粘贴你上一次复制的字符。
         * 给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 'A'。输出能够打印出 n 个 'A' 的最少操作次数。
         *
         *
         * @param: [n]
         * @return: int
         * @auther: smallfish
         * @date: 2020-03-22 19:53
         */
        int result = 0;
        int start = 2;
        while (start > 0) {
            while (n % start == 0) {
                n = n / start;
                result += start;
            }
            start += 1;
            if(n==1){
                break;
            }
        }
        return result;
    }