整数唯一分解定理

1、质因子分解

每个合数都可以写成若干质数因子相乘的形式，这种形式叫做质因子分解。

例如： $60=2 \times 2 × 3 × 5$ 。

分解质因数只针对合数，因为质数没有其它质因子。

假设$n = a_1^{p_1} \times a_2^{p_2} \times ... \times a_k^{p_k} $的质因子分解形式，其中 $a_1 ... a_k$ 为从小到大的质因子。

那么我们可以循环从 $n$ 中剥出 $a_i$ ，以 2为例：

while(n % 2== 0) {
  cout<<2 << " ";
  n /= 2;
}

质因子从小到大被剥离，最后 n 就变成了 1，此时就循环完成了。

例如：100 = 2x2x5x5，剥出 2 2 5 5 后，n就剩下1.

算法代码如下：

for(int i=2; n>1; i++)
    while(n%i==0) {
      cout<<i<<" ";
      n /= i;
    }

性能：如果n是一个很大的质数例如1e9+7，则需要循环n次，会超时。

先用欧拉筛法保存每个数的最小质因子。

然后循环剥离每次n的最小质因子。