Spoj FACTCG2 - Medium Factorization Solution

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

 Solution in C++: 

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

///**********ALLAH IS ALMIGHTY************///

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define sf scanf

#define pf printf

const int MAX = 5000;

bool prime[MAX];

vector <int> v;

void sieve ()

{

    int i,j;

    prime[0] = prime[1] = true;

    v.pb(2);

    for (i=4; i<MAX; i+=2)

        prime[i] = true;

    for (i=3; i*i<=MAX; i+=2)

        if (!prime[i])

            for (j=i*i; j<MAX; j+=2*i)

                prime[j] = true;

    for (i=3; i<MAX; i+=2)

        if (!prime[i])

            v.pb(i);

}

 

int main ()

{

    sieve ();

    int n,i,len;

    while (sf ("%d",&n) != EOF)

    {

        vector <int> P;

        P.pb(1);

        for (i=0; v[i]*v[i]<=n; i++)

        {

            while (n % v[i] == 0)

            {

                P.pb(v[i]);

                n /= v[i];

            }

        }

        if (n > 1)

            P.pb(n);

        len = P.size();

        for (i=0; i<len; i++)

        {

            pf ("%d",P[i]);

            if (i == len-1)

                pf ("\n");

            else

                pf (" x ");

        }

    }

    return 0;

}