LightOj 1035 - Intelligent Factorial Factorization

/*

    Lightoj 1035 - Intelligent Factorial Factorization
    Verdict:: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define loop (i,n) for (i=0;i<n;i++)
#define LL long long
#define L long
#define nl puts("")
#define MX 1000005
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()

using namespace std;

bool stats[N];
//int i,j,k,vpsize,qrt;
int vpsize;
vector <int> vp;
vector <int> s;

struct my
{
    int a;
    int b;
};
void prime()
{
    int i,j,k,qrt;

    for (i=4;i<=N;i+=2)
    {
        stats[i] = true;
    }

    vp.push_back(2);

    qrt = (int) sqrt(double(N));

    for (i=3;i<=qrt;i+=2)
    {
        if (!stats[i])
        {
            for (j=i*i;j<=N;j+=i+i)
            {
                stats[j] = true;
            }
        }
    }

    for (i=3;i<=N;i+=2)
    {
        if (!stats[i])
        {
            vp.push_back(i);
        }
    }

    vpsize = vp.size();
}

void primefacto(int n)
{
    for (int i=0;i<vpsize;i++)
    {
        while (n%vp[i]==0)
        {
            if (n%vp[i]==0)
            {
                s.push_back(vp[i]);
                n/=vp[i];
            }

            if (n==1 or n==0) break;
        }
    }
}

int main()
{
    int tc,t,d;
    prime();
    map <int,int>m;
    map <int,bool> mp;
    vector <int> dis;
    my ar[N];
    //for (int i=0;i<vpsize;i++) cout << vp[i] << " ";
    sf ("%d",&tc);

    for (t=1;t<=tc;t++)
    {
        int n,cnt=0,len=0;
        sf ("%d",&n);

        for (int i=2;i<=n;i++)
        {
            if (!stats[i])
            {
                s.push_back(i);
            }

            else
            {
                primefacto(i);
            }
        }

        //for (int i=0;i<s.size();i++) cout << s[i] << " ";

        sort(s.begin(),s.end());
        //for (int i=0;i<s.size();i++) cout << s[i] << " ";

        /*for (int i=0;i<s.size();i++)
        {
            m[s[i]]++;
            cout << s[i] << " " << "(" << m[s[i]] << ")" << " ";
            //d = s[i];
        }*/

        for (int i=0;i<s.size();i++)
        {
            if (!mp[s[i]])
            {
                dis.push_back(s[i]);
            }

            mp[s[i]] = true;
        }

        //for (int i=0;i<dis.size();i++) cout << dis[i] << " ";
        for (int i=0;i<dis.size();i++)
        {
            cnt = 0 ;

            for (int j=0;j<s.size();j++)
            {
                if (dis[i] == s[j])
                {
                    cnt++;
                }
            }

            ar[len].a = dis[i];
            ar[len].b = cnt;
            len++;
        }

        int stlen = len;

        pf ("Case %d: %d = ",t,n);

        for (int i=0;i<len;i++)
        {
            pf ("%d (%d)",ar[i].a,ar[i].b);
            if (stlen > 1)
            {
                //pf (" ");
                pf (" * ");
                stlen--;
            }
        }

        pf ("\n");

        mp.clear(); s.clear(); dis.clear();
    }

    return 0;
}