Uva 10780 - Again Prime? No Time.

/*

    Author: Pranta Sarker
    Problem: Uva 10780 Again Prime? No time
    Verdict: Accepted
    Time: 0.000

Given m and n. Find out the maximum power of m which can divide n! .
This method is simple. Find how many prime factors are exist in n! . Then divide the power for every prime factors of n! by
the power of prime factors of m. Find the minimum value between them.
Look, m=150, n=10! then, 150=2^1 * 3^1 * 5^2 and 10! = 2^8 * 3^4 * 5^2 * 7^1;
So, what will be the maximum power of m to can divide n! ? Definitely 1. Because, 2^1 is exist as 8 times in 2^8,
3^1 is exist as 4 times in 3^4 and 5^2 is exist as 1 times in 5^2. As 150^8 > 10! and 150^4 > 10! so, the answer will be
1, cause only power 1 of 150 can divide 10!.
m will not be divided if the minimum value is 0.


*/

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<bitset>

#define limit 10050
#define sf scanf
#define pf printf

using namespace std;

int psz=limit, prm[limit], plen=0;

bitset<limit>bs;

typedef long long LL;
typedef map<int,int>mpii;

void sieve()
{
    LL i,j;
    bs.set();
    bs[0] = bs[1] = 0;

    for(i=2; i<limit; i++)
    {
        if(bs[i])
        {
            prm[plen++] = i;

            for(j=i*i; j<limit; j+=i)
            {
                bs[j] = 0;
            }
        }
    }

    //for(i=0;i<100;i++)cout<<prm[i]<<" ";
}

int aryn[limit];

void fact_factors(int num, int p)
{
    int cnt=0;

    while(num > 0)
    {
        cnt+=(num/p);
        num/=p;
    }

    aryn[p] = cnt;
}

void solution(int m)
{
    int i, cnt=0, ans=50000;

    for(i=0; i<plen and prm[i] * prm[i] <= m; i++)
    {
        if(!(m % prm[i]))
        {
            cnt=0;

            while(!(m % prm[i]))
            {
                cnt+=1;
                m/=prm[i];
            }

            ans = min(ans, aryn[prm[i]] / cnt);
        }
    }

    if(m > 1)
    {
        ans = min(ans, aryn[m]);
    }
    //cout << ans;

    if(!ans or ans==50000)
    {
        pf("Impossible to divide\n");
    }

    else
    {
        pf("%d\n",ans);
    }
}

int main()
{
    sieve();
    int t, tc=0;
    sf("%d",&t);
    while(t--)
    {
        memset(aryn, 0, sizeof(aryn));
        int m,n , i;
        sf("%d %d",&m,&n);

        pf("Case %d:\n",++tc);

        if(m==1 or n==1)
        {
            pf("Impossible to divide\n");
            continue;
        }

        for(i=0; prm[i]<=n; i++)
        {
            fact_factors(n, prm[i]);
        }

        solution(m);
    }

    return 0;
}