质因子分解

所谓质因子分解是指将一个正整数n写成一个或多个质数的乘积的形式，
例如6=2x3, 8=2x2x2, 180=2x2x3x3x5,或者我们也可以写成指数的形式，例如6=2¹x3¹, 8= 2³, 180= 2² x3²x5¹.
显然，由于最后都要归结到若干不同质数的乘积，因此不妨先把素数表打印出来。而打印素数表的方法上面已经阐述，
下面我们主要就质因子分解本身进行讲解。
注意：由于1本身不是素数，因此它没有质因子，下面的讲解是针对大于1的正整数来说的，
而如果有些题目中要求对1进行处理，那么视题目条件而定来进行特判处理。
由于每个质因子都可以不止出现一次，因此不妨定义结构体 factor,用来存放质因子及其个数，
如下图所示:

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

考虑到 2x3x5x7x11x13x17x19x23x29就已经超过了int 范围，
因此对一个int型范围的数来说,fac数组的大小只需要开到10就可以了。

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

• 枚举1 ~ sqrt(n)范围内的所有质因子p,判断p是否是n的因子。
  如果p是n的因子，那么给fac数组中增加质因子p,并初始化其个数为0,然后，
  只要p还是n的因子，就让n不断除以p,每次操作令p的个数加1,直到p不再是n的因子为止。

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

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

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

至此,fac数组中存放的就是质因子分解的结果，时间复杂度为O(n^1/2)

#include<cstdio>
#include<cmath>
struct factor
{
	int x;//质因子
	int cnt;//个数
}fac[100];
int b[1000005];
int k=0;
bool find(int n)//判断是不是质数
{
	for(int i=2;i<=sqrt(n);i++)
	{
		if(n%i==0)
			return false;
	}
	return true;
}
int main(void)
{
	long long int n;
	scanf("%lld",&n);
	long long int i,num,temp;
	i=num=0;
	temp=n;
    if(n==1)
	{
		printf("1=1\n");
		return 0;	
	}
	for(int i=2;i<=sqrt(n);i++)//填写质数表
	{
		if(find(i))
			b[k++]=i;	
	}
	for(i=0;i<k;i++)
	{
		if(n%b[i]==0)
		{
			fac[num].x=b[i];//记录该质因子
			fac[num].cnt=0;
			while( n%b[i] == 0 )//计算出质因子prime[i]的个数
			{
				fac[num].cnt++;
				n=n/b[i];
			}
			num++;//不同质因子个数加1
		}
	}	
	if(n!=1)//如果无法被根号n以内的质因子除尽
	{
		fac[num].x=n;//那么一定有一个大于根号n的质因子
		fac[num++].cnt=1;
	}
	printf("%lld=",temp);
	for(i=0;i<num-1;i++)
	{
		if(fac[i].cnt>1)
		{
			printf("%d^%d*",fac[i].x,fac[i].cnt);
		}
		if(fac[i].cnt==1)
			printf("%d*",fac[i].x);
	}
	if(fac[i].cnt!=1)
	{
		printf("%d^%d\n",fac[i].x,fac[i].cnt);
	}
	else
		printf("%d\n",fac[i].x);
	return 0;
}