View Code of Problem 91

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
const int maxn=10010;
int prime[10010];
int pnum=0;
bool isPrime(int n)
{
	if(n==1)return false;
	int sqr=(int)sqrt(n*1.0);
	for(int i=2;i<=sqr;i++)
	{
		if(n%2==0)
		return false;
	}
	return true;
}
void FindPrime()
{
	for(int i=1;i<maxn;i++)
		if(isPrime(i)==true)
			prime[pnum++]=i;
}

struct factor{
	int x,cnt;
}fac[10];
int main()
{
	FindPrime();
	int n,num=0;
	scanf("%d",&n);
	if(n==1)printf("1==1");
	else{
		printf("%d=",n);
		int sqr=(int)sqrt(n*1.0);
	for(int i=0;i<pnum&&prime[i]<=sqr;i++)
	{
		if(n%prime[i]==0){
			fac[num].x=prime[i];
			fac[num].cnt=0;
			while(n%prime[i]==0){
			fac[num].cnt++;
			n=n/prime[i];
			}
			num++;
		}
		if(n==1)break;
	}
	if(n!=1)
	{
		fac[num].x=n;
		fac[num++].cnt=1;
	}
	printf("%d",fac[0].x);
	fac[0].cnt--;
	int a=0;
	while(fac[a].cnt--)
	{
		printf("*%d",fac[a].x);
		if(fac[a].cnt==0)
			a++;
	}
	}

	system("pause");
}