【概述】

• 惟一分解定理：若整数 a ≥ 2，那么 a 一定可以表示为若干个素数的乘积 (惟一的形式)。
  如：1260 = 2 * 2 * 3 * 3 * 5 * 7 = 2² * 3² * 5 * 7

【一】

Pollard Rho快速因数分解。该算法时间复杂度为 O(n^(1/4))。

程序分析：对 n 进行分解质因数，应先找到一个最小的质数 i，然后按下述步骤完成：

1. 如果这个质数 i 恰等于 n，则说明分解质因数的过程已经结束，打印输出即可。
2. 如果 n != i，但 n 能被 i 整除，则应打印输出 i 的值，并用 n 除以 i 的商，作为新的正整数n，重复执行第一步。
3. 如果 n 不能被 k 整除，则用 k+1 作为k的值，重复执行第一步。

代码如下：

void fun(int n)
{
	printf("%d = ",n);
	for(int i=2;i<=n;i++)
	{
		while(n!=i)
    	{
	    	if(n%i==0)
	    	{
	    		printf("%d * ",i);
	        	n = n/i;
	      	}
	    	else
	        	break;
    	}
	}
	printf("%d",n);
}

【二】

• 将任意的 n 分解为质因数的乘积，要从最小的质数开始，那么，我们就不妨从2开始试除，能整除就输出2，再对商继续试除，直到不再含有因子2；然后用下一个质数反复试……再用下一个质数试除……直到商为1，停止操作。

• 这里，质因数的递增，是一层循环，每一个质因数的反复试除，又是一层循环。因此，使用两层循环来解决。

void fun(int n)
{
	cout<<n<<" = ";
	int i = 2;
	do{
		while(n%i==0)	//n能被i整除，就重复做除法操作 
		{
			cout<<i;
			n /= i;
			if(n!=1)
				cout<<" * ";
		}
		i++;
	}while(n!=1);	//n没有除尽，就重复操作 
	
}

【三】

• 所谓质因子分解是指将一个正整数 n 写成一个或多个质数的乘积的形式，例如 6 = 2 x 3，8 = 2 x 2 x 2，180 = 2 x 2 x 3 x 3 x 5。或者我们也可以写成指数的形式，例如 6 = 2¹ x 3¹， 8 = 2³，180 = 2² x 3² x 5¹。

• 显然，由于最后都要归结到若干不同质数的乘积，因此不妨先把素数表打印出来。下面我们主要就质因子分解本身进行讲解。注意：由于 1 本身不是素数，因此它没有质因子，下面的讲解是针对大于 1 的正整数来说的，而如果有些题目中要求对 1 进行处理，那么视题目条件而定来进行特判处理。

• 由于每个质因子都可以不止出现一次，因此不妨定义结构体 factor，用来存放质因子及其个数，如下所示：

struct factor{
int x, cnt; //x 为质因子，cnt为其个数
}fac[10]; 

• 这里 fac[ ] 数组存放的就是给定的正整数 n 的所有质因子。例如对 180 来说，fac 数组如下：

fac[0].x = 2;
fac[0].cnt = 2;

fac[1].x = 3;
fac[1].cnt = 2;

fac[2].x = 5;
fac[2].cnt = 1;

• 考虑到 2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 就已经超过了 int 范围，因此对一个 int 型范围的数来说，fac 数组的大小只需要开到10就可以了。

• 前面提到过，对一个正整数n来说，如果它存在1和本身之外的因子，那么一定是在 sqrt(n) 的左右成对出现。而这里把这个结论用在“质因子”上面，会得到一个强化结论：对一个正整数 n 来说，如果它存在 [2, n] 范围内的质因子，要么这些质因子全部小于等于sqrt(n)，要么只存在一个大于 sqrt(n) 的质因子，而其余质因子全部小于等于sqr(n)。这就给进行质因子分解提供了一个很好的思路：

1、枚举 1~ sqrt(n) 范围内的所有质因子p，判断 p 是否是 n 的因子。

• 如果 p 是 n 的因子，那么给 fac 数组中增加质因子p，并初始化其个数为0。然后，只要 p 还是 n 的因子，就让 n 不断除以 p，每次操作令 p 的个数加 1，直到 p 不再是 n 的因子为止。

if(n%prime[i] == 0) //如果 prime[i] 是n的因子
{ 
	fac[num].x = prime[i]; // 记录该因子
	fac[num].cnt = 0;
	while(n%prime[i] == 0)  //计算出质因子prime[i]的个数
	{
		fac[num].cnt++;
		n /= prime[i];
	}
	num++; //不同质因子个数加 1
}

• 如果ρ不是n的因子，就直接跳过。

2、如果在上面步骤结束后 n 仍然大于1，说明 n 有且仅有一个大于 sqrt(n) 的质因子(有可能是 n 本身)，这时需要把这个质因子加入 fac 数组，并令其个数为1。

if(n != 1) //如果无法被根号n以内的质因子除尽
{ 
	fac[num].x = n; //那么一定有一个大于根号n的质因子
	fac[num++].cnt = 1:

至此，fac 数组中存放的就是质因子分解的结果，时间复杂度是O(√n)。