prime factors.cpp

#include<bits/stdc++.h>

using namespace std;

/*

        Bismillahir Rahmanir Rahim
        Problem :
        Problem Link :
        Topics :
        Solver : Masud Parves
        I Love Code More than Sharks Love Blood <3
*/


#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(a)  a.begin(), a.end()


#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("d",&a,&b)
#define sfff(a,b,c)     scanf("d%d",&a,&b,&c)

#define f0(i,b) for(int i=0;i<(b);i++)
#define f1(i,b) for(int i=1;i<=(b);i++)
#define f2(i,a,b) for(int i=(a);i<=(b);i++)
#define fr(i,b,a) for(int i=(b);i>=(a);i--)

#define mx  50000
#define TEST_CASE(t) for(int z=1 ; z<=t ; z++)
#define PRINT_CASE printf("Case %d: ",z)
#define NOT_VISITED 0
#define IS_VISITED 1



int fx[4]= {1,-1,0,0};
int fy[4]= {0,0,1,-1};


const double PI = acos(-1.0);
const double EPS = 1e-6;
const int MOD = (int)1e9+7;
const int maxn = (int)2e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, int> plli;
typedef pair<int, ll> pill;

vi prime;
bool flag[mx];

void sieve_method()
{
    //prime.push_back(0);
    prime.push_back(2);

    for(ll i=3 ; i*i<=mx ; i+=2)
    {
        if(flag[i]==false)/// hare i is prime
        {
            prime.push_back(i);
            for(ll j = i*i; j <= mx; j +=(i+i))
            {
                flag[j] = true;
            }
        }
    }
//    cout<<prime.size()<<endl;
//    for(int i=0; i<prime.size() ; i++)
//    {
//        cout<<prime[i] << " ";
//    }
}

vector<int> prime_factors(int n)
{
    vector<int> factors;
    int pf_index = 0;
    //long pf = prime[pf_index];

    for(int i=0;prime[i] * prime[i] <= n ; i++)
    {
        if(n % prime[i] == 0)
        {
            while(n % prime[i] == 0)
            {
                n /= prime[i];
                factors.push_back(prime[i]);
            }
        }
        if(n>1)
            factors.push_back(n);

    }

    return factors;
}




int main()
{

    //CIN
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    sieve_method();

    int n;
    while(scanf("%d", &n)!=EOF)
    {

        if(n == 0)
            break;

        vector<int> factors = prime_factors(fabs(n));

        if(n<0)
            printf("%d = -1 x %d", n, factors[0]);
        else
            printf("%d = %d", n, factors[0]);
        for(int i=1 ; i<factors.size() ; i++)
            printf(" x %d", factors[i]);
        printf("\n");
        factors.clear();
    }
    return 0;
}