[算法/模板]质因数分解

大家好，欢迎来到IT知识分享网。

[TOC]
###**一、质因数分解的基本定理**
$\forall N \in (1,\infty)$都能唯一分解成有限个质数的乘积，可写作：
$$N=P_1^{c_1}P_2^{c_2}...P_m^{c_m}$$
其中$c_i$为正整数，$P_i$都是质数，且满足$P_1\lt P_2\lt ...\lt P_m$。

我们可以扫描2~$\sqrt N$的每个数k，若k能整除N，那么我们从N中除掉所有的因子k，同时累计被除去的k的个数。
因为一个合数的因子一定在扫描到这个合数之前就从N中被除去了，因此扫描到能整除N的数一定是质数。
需要注意的是，若最终N没有被[2,$\sqrt N$]的数整除，则N为质数，直接累计就可以了。
综上，质因数分解的时间复杂度为$O(\sqrt N)$。
###**二、模板-质因数分解**
代码如下：
```
inline void Divide(){
	cnt=0;
	for(int i=2;i<=sqrt(n);i++){
		if(n%i==0){
			p[++cnt]=i;
			while(n%i==0){
				num[cnt]++;
				n/=i;
		        }
           }
       }
	if(n>1){
		p[++cnt]=n;num[cnt]=1;
	}
}//其中p为底数，num为对应的指数 
```