View Code of Problem 91

#include<bits/stdc++.h>
using namespace std;
#define max 100001
struct zhishu{
	int n,cnt;
}fac[10];
bool jud(int);
void show();
int cnt_sushu = 0,sushu[max] = { };
int main(){
	show();
	int n,tmp_n,cntF = 0,fin[20] = { },finall = 0;
	cin>>n;
	tmp_n = n;
	if(n==1) cout<<"1=1";
	else{
//		cout<<n<<"=";
		int op = (int)sqrt(1.0*n);	
		for(int i = 0;i < cnt_sushu && i <= op ; i++ ){
			if( n % sushu[i] == 0 ){
				fac[cntF].n = sushu[i];
				fac[cntF].cnt = 0;
			while( n % sushu[i] == 0){
				fac[cntF].cnt++;
				n/=sushu[i];
			}
			cntF++;
		}
			if( n == 1 )break;
		}
		if(n!=1){
			fac[cntF].n = n;
			fac[cntF].cnt = 1;
		}
//	for(int i = 0;i<cntF;i++)cout<<fac[i].n<<"--->"<<fac[i].cnt<<endl;
		for(int i = 0;i<cntF;i++){
			if(fac[i].n != 0){
				fin[finall++] = fac[i].n;
				fac[i].cnt--;
			}
			if(fac[i].cnt > 0 ){
				while(fac[i].cnt--)fin[finall++] = fac[i].n;
			}
		}	
	
		cout<<tmp_n<<"=";
		for(int i = 0;i<finall;i++){
			if(i==finall-1)cout<<fin[i];
			else cout<<fin[i]<<'*';
		}
//		for(int i = 0;i<finall;i++)cout<<fin[i]<<" ";
		
		
//		for(int i = 0;i<cntF;i++){
//			if(i>0) cout<<'*';
//			cout<<fac[i].n;
//			if(fac[i].cnt>1)
//			cout<<'^'<<fac[i].cnt; 
//		}
	}
	return 0;
}






void show(){
	for(int i = 2;i<max;i++){
		if(jud(i))sushu[cnt_sushu++] = i;
	}
}
bool jud(int n){
	if(n == 1)return false;
	int op = (int)(sqrt(1.0*n));
	for(int i = 2;i <= op;i++){
		if( n % i == 0 ) return false;
	}
	return true;
}