1035 - Intelligent Factorial Factorization

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

Solution Idea : Need to prime factorize n with faster factorial factorize method.

Solution :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

bool status[110];

vector<ll int>prime;

void sieve()
{
    int n=110;
    int sq=sqrt(n);

    for(int i=4; i<=n; i=i+2) status[i]=true;

    for(int i=3; i<=sq; i=i+2)
    {
        if(status[i]==false)
        {

            for(int j=i*i; j<=n; j=j+i) status[j]=true;
        }
    }
    status[1]=1;
    status[0]=1;

    prime.push_back(2);

    for(int i=3; i<=n; i=i+2)
    {
        if(status[i]==0) prime.push_back(i);
    }
}

void fact (ll int n )
{
    ll int ok=0;
    for ( ll int i = 0; i < prime.size() and prime[i]<= n; i++ )
    {
        ll int x = n;
        ll int freq = 0,c;

        while ( x / prime[i] )
        {
            freq += x / prime[i];
            x = x / prime[i];
        }

        if(ok==0)
        {

            printf("%lld (%lld)", prime[i], freq );
            ok++;
        }
        else
        {
            printf(" * ");
            printf("%lld (%lld)",prime[i],freq);

        }
    }
}
int main()
{
    sieve();

    ll int t,n;
    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld",&n);
        printf("Case %lld: %lld = ",ca,n);
        fact(n);
        printf("\n");
    }
}