Spoj - FACT0- Integer Factorization

Problem Link: https://www.spoj.com/problems/FACT0/

Idea : Simple Prime factorization problem.Do not use Sieve or you will get TLE.

Code First Then See Solution

Code:

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main()

{

    ll n;

    while(cin>>n)

    {

        if(n==0)

            break;

        ll cnt=0;

        while(n%2==0)

        {

            cnt++;

            n/=2;

        }

        if(cnt>0)

            cout<<"2"<<"^"<<cnt<<" ";

        ll x=3;

        while(x*x<=n)

        {

            cnt=0;

            while(n%x==0)

            {

                cnt++;

                n/=x;

            }

            if(cnt>0)

                cout<<x<<"^"<<cnt<<" ";

            x+=2;

        }

        if(n!=1)

            cout<<n<<"^"<<1<<endl;

        else

            cout<<endl;

    }

    return 0;

}