难度: Medium
最初记事本上只有一个字符 '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
提示：
1 <= n <= 1000运行时间: 31 ms
内存: 16.0 MB
import math as m
class Solution:
def minSteps(self, n: int) -> int:
r = 0
for i in range(2, int(m.sqrt(n) + 2)):
while not n % i: # 能整除
n //= i
r += i
if n > 2:
r += n
return r
这个题解采用的是素数分解的思路。对于任意一个大于1的整数n，可以将其分解为一系列素数的乘积。例如，12=2*2*3。题目要求的是打印出n个'A'所需的最少操作次数，实际上就等于n的素数分解式中所有素数的和。因为对于一个素数因子p，我们需要执行p次'Paste'操作和一次'Copy All'操作，总共p+1次操作。而n的素数分解的结果就是这些素数因子的集合，操作次数就是这些素数的和。题解中使用了从小到大枚举素数因子的方法，依次将n除以素数，同时累加操作次数，最后如果剩余的n大于1，则说明是一个大于sqrt(n)的素数因子，需要再加上n。
时间复杂度: O(sqrt(n) * log n)
空间复杂度: O(1)
import math as m
class Solution:
def minSteps(self, n: int) -> int:
r = 0
for i in range(2, int(m.sqrt(n) + 2)):
while not n % i: # 能整除
n //= i # 除以当前素数因子
r += i # 累加操作次数
if n > 2:
r += n # 剩余的大于sqrt(n)的素数因子
return r
在题解中，每个素数因子p的操作代表了用最优策略创建p个'A'的步骤。首先，我们需要有一个'A'，然后执行一次`Copy All`将其复制，接下来进行p-1次`Paste`操作，将这个'A'粘贴p-1次，从而累计获得p个'A'。因此，对于每个素数因子p，总共需要1次`Copy All`和p-1次`Paste`，共p次操作。但考虑到最初的'A'需要首次创建，所以每个素数因子的总操作次数实际上是p。因此，通过素数分解，我们将n分解成多个素数因子的乘积，每个素数因子p的操作步骤相当于是创建了p个'A'。最终，所有这些操作步骤的累加即为解决问题所需的最小操作次数。
实际上，每个素数因子p的操作次数应该是p次，而不是p+1次。这包括1次`Copy All`和p-1次`Paste`。初始的一个'A'不需要通过`Copy All`和`Paste`获得，因此对于每个因子p，总共需要p次操作来达到复制p个'A'的目的。这可能是对题解的解释中的一个小误会。
当在计算过程中，n仍大于2时直接将n加入结果，这是基于假设n是一个素数的前提。题解通过素数分解，从最小的素数开始除尽n中所有可整除的素数因子，最终如果n大于2，则剩余的n不能被任何小于或等于它的素数整除，因此n本身必须是一个素数。这样的处理是确保所有因素都考虑到，没有遗漏任何操作步骤。
题解采用的素数分解算法在执行上是有效的，但在特定情况下，尤其是当n非常大时，其效率可能会成问题。素数分解的过程需要迭代到sqrt(n)，这对于非常大的n可能会导致执行时间较长。此外，如果未优化求素数的过程，反复检测每个数是否为素数也会增加计算负担。尽管如此，对于大多数实际问题规模，这种方法应该是可行的。然而，对于极端情况或者需要高效处理大量数据的情况，可能需要更高效的算法或者实现优化。