Light OJ 1215 Finding LCM

#include<bits/stdc++.h>
#define mx 10000000
using namespace std;
bool prime[mx];
int arr[700000],l;
void sieve()
{
    long long int i,j;
    l=0;
    for(i=4;i<=mx;i+=2)
        prime[i]=1;
    int s=sqrt(mx);
    for(i=3;i<=s;i+=2)
    {
        if(prime[i]==0)
        {
            for(j=i*i;j<=mx;j+=2*i)
            {
                prime[j]=1;
            }
        }
    }
    prime[1]=1;prime[0]=1;
    for(i=0;i<=mx;i++)
    {
        if(prime[i]==0)
            arr[l++]=i;
    }
}
long long int count_pf(long long int a,long long int b,long long int c)
{
    long long int i,j,counta,countb,countc,m,ans=1;
    for(i=0;;i++)
        {
            if(arr[i]>c)
                break;
            counta=0;
            countb=0;
            countc=0;
            m=arr[i];
            if(c%m==0)
            {
                while(1)
                {
                    if(c%m==0)
                    {
                        c=c/m;
                        countc++;
                    }
                    else
                        break;
                    if(a%m==0)
                    {
                        a=a/m;
                        counta++;
                    }
                    if(b%m==0)
                    {
                        b=b/m;
                        countb++;
                    }
                }
                if(max(counta,countb)<countc)
                {
                 
                    for(j=1;j<=countc;j++)
                    {
                        ans=ans*m;
                    }
                }

            }
        }
        return ans;
}
int main()
{
    sieve();
    long long int i,j,k,m,n,p,A,B,C,LCM,test,count,ans;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>A>>B;
        cin>>LCM;
        cout<<"Case "<<k<<": ";
        if(LCM%A!=0||LCM%B!=0)
        {
            cout<<"impossible"<<endl;
        }
        else
        {
            cout<<count_pf(A,B,LCM)<<endl;
        }
    }
    return 0;
}