using namespace std;

#define ll long long

#include <stdio.h>
#include <fstream>

FILE *fin=fopen("gfact.in","r"),
     *fout=fopen("gfact.out","w");
     
typedef struct 
 {
   int n,p;
 } data;       
     
ll p;
int q,m,b[100];
data d[100];     
    
void descompune()
{
 int ind=0,i=2,ct;
 while (p>1)
  {
    if (p%i==0) {
      ct=0;     
      ind++;      
      while (p%i==0) { p/=i; ct++; }
       d[ind].n=i; d[ind].p=ct;
     }
    i++;
  }     
 m=ind;
 for (i=1; i<=m; i++)
  d[i].p*=q;   
}   
 
int power(int a, int b)
{
  int ct=0,c=b;
   while (b<=a) { ct+=a/b; b*=c; }
  return ct;
}  
   
 
void cautafact()
{
  int i,li,lf,mj=0,x,t,sol=0;
  for (i=1; i<=m; i++)
   {
     li=1; lf=d[i].p;
     while (li<=lf)
      {
       mj=(li+lf)/2;
       x=mj*d[i].n;
       t=power(x,d[i].n);
       if (t<d[i].p) li=mj+1;
       if (t>d[i].p) lf=mj-1;
       if (t==d[i].p) break;
      }
     if (power(mj*d[i].n,d[i].n)>=d[i].p) b[i]=mj*d[i].n; 
      else b[i]=(mj+1)*d[i].n;
     if (power((mj-1)*d[i].n,d[i].n)>=d[i].p) b[i]=(mj-1)*d[i].n;  
   }                   
  for (i=1; i<=m; i++)
   if (b[i]>sol) sol=b[i];
  fprintf(fout,"%d\n",sol);
}
    
int main()
{
    
    fscanf(fin,"%lld %d",&p,&q);
    
    descompune();
    cautafact();
    
    fclose(fin); fclose(fout);
    
    return 0;
    
}