UVA 583 Prime Factors (UVALive 5406, Regionals 1997 >> North America - East Central NA)

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / hackerrank / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

bool status[MX];
vector<int>prime;
int pl;

void seive(int n)
{
    int sq=sqrt(n);
    prime.push_back(2);
    for(int i=3;i<=sq;i+=2)
        if(!status[i])
            for(int j=i*i;j<=n;j+=i)
                status[j]=true;
    for(int i=3;i<=n;i++)
        if(!status[i])
            prime.push_back(i);
    pl=prime.size();
return;
}

vector<int> divisor(int n)
{
    vector<int>div;
    if(n<0)
    {
        n=-n;
        div.push_back(-1);
    }
    int sq=sqrt(n);
    for(int i=0;i<pl && prime[i]<=sq;i++)
    {
        while(n%prime[i]==0)
        {
            n/=prime[i];
            div.push_back(prime[i]);
        }
        sq=sqrt(n);
    }
    if(n!=1) div.push_back(n);
return div;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n, tc, kk=1;
    string s;
    seive(MX-5);
    while(cin>>n && n)
    {
        if(n==1)
        {
            cout<<n<<" = "<<n<<"\n";
            continue;
        }
        vector<int>ans=divisor(n);
        cout<<n<<" = "<<ans[0];
        for(int i=1;i<ans.size();i++)
            cout<<" x "<<ans[i];
        cout<<"\n";
    }
return 0;
}