LC.P650[只有两个键的键盘]

方法一：数学

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minSteps(int n) {
        int ans = 0;
        for (int i = 2; i * i <= n; ++i) {
            while (n % i == 0) {
                n /= i;
                ans += i;
            }
        }
        if (n > 1) {
            ans += n;
        }
        return ans;
    }
}
  • 时间复杂度：$O(\sqrt{n})$
  • 空间复杂度：$O(1)$