LightOJ - 1035 - Intelligent Factorial Factorization

Problem Link: http://lightoj.com/volume_showproblem.php?problem=1035


Code First Then See Solution

Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 150

char a[mx];
vector <int> v;

void sieve()
{
    memset(a,0,sizeof(a));
    for(int i=4;i<=mx;i+=2)
        a[i]=1;
    for(int i=3;i<=sqrt(mx);i++)
    {
        if(a[i]==0)
        {
            for(int j=i*i;j<=mx;j+=i)
                a[j]=1;
        }
    }
    v.push_back(2);
    for(int i=3;i<=mx;i+=2)
        if(a[i]==0)
           v.push_back(i);
}

int main()
{
    int t,m=0;
    cin>>t;
    sieve();
    while(t--)
    {
        m++;
       int n;
       cin>>n;
       cout<<"Case "<<m<<": "<<n<<" = ";
       int coun=0;
       vector <pair <int,int>> p;
       for(int i=0;v[i]<=n;i++)
       {
         int f=n;
         coun=0;
         while(f>=v[i])
         {
             f/=v[i];
             coun+=f;
         }
         p.push_back(make_pair(v[i],coun));
       }
       vector <pair <int,int>>:: iterator it;
       //int j=0;
       cout<<p[0].first<<" ("<<p[0].second<<")";
       for(int i=1;i<p.size();i++)
       {
          cout<<" * "<<p[i].first<<" ("<<p[i].second<<")";
       }
       cout<<endl;
    }
    return 0;

}