分解的写法

分解的标准套路：从最小的质数 2 开始试除，能除尽就一直除，直到除不动，再换下一个数继续。为什么换下一个数时不用管它是不是质数？因为轮到 $i$ 时，比 $i$ 小的质因数早被除干净了，$i$ 若还能整除，它必然是质数。

以 100 为例：先用 2 除，$100\to 50\to 25$（除了两次，得 $2^2$）；2 除不动换 3，除不尽；换 4，此时 25 已不含 2，4 也除不尽；到 5，$25\to 5\to 1$（得 $5^2$）。所以 $100=2^2\times 5^2$。

for (int i = 2; i * i <= n; i++)
    while (n % i == 0) { cout << i << " "; n /= i; }
if (n > 1) cout << n << " ";   // 剩下的一定是质数

复杂度 $O(\sqrt{n})$：外层只需到 $\sqrt{n}$。常见坑：忘了收尾的 if (n > 1)，会漏掉大于 $\sqrt{n}$ 的那个质因数（如 $14=2\times 7$ 里的 7）；用 if 代替 while 会导致重复质因数只除一次。