# Write a program to Calculate Prime Factor of a Number

//Write a program to calculate prime factor of a number
#include<stdio.h>
#include<math.h>
#define SIZE_N 100000
#define SIZE_P 66457

bool flag [SIZE_N] ;
int prime [SIZE_P] ;

void seive ()
{
int i,j,r,c=0,p ;
for (i=3;i<=SIZE_N;i+=2)  flag[i] = true;

flag[2]=true;
prime[c++]=2;
p=SIZE_N+1;
for(i=3;i<p;i+=2)
{
if ( flag[i] )
{
prime[c++]=i;
if ( SIZE_N / i >= i )
{
r=i*2;
for(j=i*i;j<p;j+=r) flag[j]=false;
}
}
}
}
int prime_factor(long num)
{
int i=0;
if(num<0)
{
printf("-1 x ");
num*=-1;
}
long base=(long)(sqrt(num)+0.005);
while(prime[i]<=base&&num>1)
{
if (num%prime[i]==0)
{
num /= prime[i];
if(num!=1) printf("%ld x ",prime[i]);//store here factor
else       printf("%ld",prime[i]);// store here factor
}
else i++;
}
if(num>1) printf("%ld",num);
return i;
}

int main()
{
long num;
seive();
while(scanf("%ld",&num) == 1 && num )
{
printf("%ld = ",num);
prime_factor(num);
printf("\n");
}
}

/*
Input:6 12 20
Output:2x3,2x2x3,2x2x5
*/