唯一分解定理

简介

唯一分解定理是数论中重要的思想之一。简述就是一个大于一的整数N,可以由他的素因子唯一构成。证明用到了反证法。

数学

假设N是大于一的正整数，我们有：

N=q1^p1*q2^p2*……*qn^pn

q1……qn是N的质因数
有如下性质：

 1. 约数个数 = (p1+1)*(p2+1)*……*(pn+1)
 2. 约数和 = (1+q1+……+q1^p1)*(1+q2+……+q2^p2)*……*(1+qn+……+qn^pn)

质因数分解

for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			a[k++]=i;//将素因数存在数组中
			while(n%i==0)n/=i;//将所有的素因数除掉
		}
		if(n==1)break;
	}
	if(n!=1)a[k++]=n;