View Code of Problem 91

#include<bits/stdc++.h>
using namespace std; 
const int maxn=100001;

int pnum=0,prime[maxn]={0};
bool p[maxn]={0};

void find_p()
{
	for(int i=2;i<maxn;i++)
	{
		if(p[i]==false)
		{
			prime[pnum++]=i;
			for(int j=i+i;j<maxn;j+=i)
			{
				p[j]=true;
			}			
		}

	}
}


struct fac{
	int prime[maxn];
	int facnum;
}factor;

void init_fac()
{
	memset(factor.prime,0,sizeof(factor.prime));
	factor.facnum=1;
}

int main()
{
	find_p();
	init_fac();
	int n;
	scanf("%d",&n);
	printf("%d=",n);
	if(n==1) printf("1");
	else
	{
		int sqr=(int)sqrt(1.0*n);
		int flag=0;
		for(int i=0;i<pnum &&prime[i]<=sqr ;i++)
		{
			while(n%prime[i]==0)
			{
				factor.prime[i]++;
				n/=prime[i];
			}
			if(i+1>factor.facnum) factor.facnum=i+1;
			if(n==1) break;	
		}
		
		for(int i=0;i<factor.facnum;i++)
		{
			while(factor.prime[i]!=0)
			{
				if(flag==0)
				{
					printf("%d",prime[i]);
					flag=1;
				}
				else
					printf("*%d",prime[i]);
				factor.prime[i]--;
			}
		}
		if(n!=1&&flag==1) printf("*%d",n);
		else if(n!=1&&flag==0) printf("%d",n);			
	}
	return 0;
}