唯一分解定理

定义：任何一个大于1的自然数N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P₁^a1P₂^a2P₃^a3......P_n^an，这里P_1<P_2<P_3......<P_n均为质数，其中指数a_i是正整数。这样的分解称为N的标准分解式

应用：

1、当一个数太大long long无法表示,而且需要和其他数约分时可以使用唯一分解定理uva10375

2、最小公倍数uva10791

3、小于n且与n互素的整数个数：欧拉函数