650. 只有兩個鍵的鍵盤

最初記事本上只有一個字符 ‘A’ 。你每次可以對這個記事本進行兩種操作：

• Copy All（復制全部）：復制這個記事本中的所有字符（不允許僅復制部分字符）。
• Paste（粘貼）：粘貼 上一次 復制的字符。
  給你一個數字 n ，你需要使用最少的操作次數，在記事本上輸出 恰好 n 個 ‘A’ 。返回能夠打印出 n 個 ‘A’ 的最少操作次數。

示例 1：輸入：3
輸出：3
解釋：
最初, 只有一個字符 'A'。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作來獲得 'AA'。
第 3 步, 使用 Paste 操作來獲得 'AAA'。
示例 2：輸入：n = 1
輸出：0

解題思路

每次將連續的字符串A分解，如果是二的倍數就是最優的，因為只需要復制粘貼兩步，如果是3的倍數，就需要復制粘貼粘貼三步。因此，我們需要將字符串分解成為盡量大的幾部分，所以我們可以從2，3，4…一直查找當前字符串能被分割為幾塊

代碼

class Solution {public int minSteps(int n) {int res=0;while(n>1){for(int i=2;i<=n;i++)if(n%i==0){n/=i;res+=i;break;}}return res;}
}