#include <fstream>

using namespace std;


ifstream cin("gfact.in");
ofstream cout("gfact.out");

int minim=1e9,n,q,factmaxim=-1e9;
int DeCateOriGasescNumarInFactorialulLuiM(int k,int m)
{int pp=k,kk=0;
    while(m>=pp)kk+=m/pp,pp*=k;
  return kk;
}

int cautare(int s,int d,int numar,int putere)
{

    if(s>d) return -1;
    else
        {
          int mm,m=(s+d)/2;
          mm=DeCateOriGasescNumarInFactorialulLuiM(numar,m);

          if(putere==mm)return m;
          else if(putere>mm)

                return cautare(m+1,d,numar,putere);






               else
                 {
                   if(m<minim)minim=m;
                   return cautare(s,m-1,numar,putere);

                 }
        }


}


int main()
{
    cin>>n>>q;
    int dq,ct,d=0;
    if(n%2==0)
    {
     while(n%2==0)n/=2,++d;
     dq=d*q;

     factmaxim=cautare(1,dq*2,2,dq);
     if(factmaxim==-1)factmaxim=minim;

     while(1)
     {   --factmaxim;
         int x=DeCateOriGasescNumarInFactorialulLuiM(2,factmaxim);
         if(x!=dq)break;

     }
     ++factmaxim;


    }


    d=3;
    while(n!=1)
    {ct=0;
     minim=1e9;
        while(n%d==0)n/=d,++ct;

      dq=ct*q;
        if(ct>0)
        {
          int j=cautare(1,dq*d,d,dq);
          if(j==-1)j=minim;

          while(1)
         {   --j;
            int x=DeCateOriGasescNumarInFactorialulLuiM(d,j);
             if(x!=dq)break;

         }
         ++j;

          if(j>factmaxim)factmaxim=j;

        }
        if(d*d>n)d=n;
        else d+=2;

    }

    cout<<factmaxim<<" ";


    return 0;
}