质因数分解

算术基本定理：任何大于 1 的整数，都能唯一地写成若干个质数相乘（不计顺序）。比如 $60=2\times 2\times 3\times 5=2^2\times 3\times 5$，$84=2^2\times 3\times 7$。这叫质因数分解，是数论题的基本工具。

"唯一"很重要：无论你按什么顺序去分解，得到的那组质因数（连同各自的个数）都是同一套。所以求最大公约数、最小公倍数、约数个数，都能从质因数入手。

// 分解 n，把质因数连同次数打印出来
for (int i = 2; i * i <= n; i++)
    while (n % i == 0) {
        cout << i << " ";
        n /= i;
    }
if (n > 1) cout << n;   // 剩下的大质因数

常见坑：分解出的是"带重复"的质因数（$60$ 里有两个 2），别只写一遍；循环用 while 把同一个质因数除干净再换下一个；最后 n>1 的判断不能漏，否则会丢掉最大的那个质因数。