UVA 10780 Again Prime? No time Solution

 Problem  Link :  https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1721

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];

ll arp[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);

        }

    }

}

void fact_factors(int num, int p)

{

    ll cnt = 0;

    while (num > 0)

    {

        cnt += (num / p);

        num /= p;

    }

    arp[p] = cnt;

}

void solution(int m)

{

    ll cn = 0, ans = 50000;

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

    {

        if (m % prime[i] == 0)

        {

            cn = 0;

            while (m % prime[i] == 0)

            {

                cn++;

                m /= prime[i];

            }

            ans = min(ans, arp[prime[i]] / cn);

        }

    }

    if (m > 1)

        ans = min(ans, arp[m]);

    if (!ans or ans == 50000)

        cout << "Impossible to divide" << endl;

    else

        cout << ans << endl;

}

int main()

{

    sieve();

    ll t, k = 0;

    scanf("%lld", & t);

    while (t--)

    {

        ll n, m;

        scanf("%lld %lld", & m, & n);

        printf("Case %lld:\n", ++k);

        memset(arp, 0, sizeof(arp));

        if (m == 1 || n == 1)

        {

            cout << "Impossible to divide" << endl;

            continue;

        }

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

        {

            fact_factors(n, prime[i]);

        }

        solution(m);

    }

}