Spoj PTIME - Prime Time Solution

 

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

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 ll long long int

const ll N=1e6;

vector<ll>prime;

ll i,j;

bool vis[N];

void sieve()

{

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

    {

        if(vis[i]==0)

        {

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

            {

                vis[j]=1;

            }

        }

    }

    prime.push_back(2);

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

    {

        if(vis[i]==0)

        {

            prime.push_back(i);

        }

    }

}

int main()

{

    ll t,n,i,mx,cnt,cn,cp;

    sieve();

    cin>>n;

    bool flag=true;

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

    {

        int sum=0, num=n;

        while(num>0)

        {

            sum+=num/prime[i];

            num/=prime[i];

        }

        if(flag)

        {

            flag=false;

            printf("%d^%d",prime[i],sum);

        }

        else printf(" * %d^%d",prime[i],sum);

    }

}