质因数分解

一句话理解

质因数分解：n 除以从小到大的质因子。

为什么要学

先筛质数再分解更快。

讲解

到 sqrt(n)，剩下大于 1 的是质数。

例子

84=2^237。

常见错误

• 循环到 n 而不是 sqrt，n=1e12 TLE。
• 把 1 分解。