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];  
int pr[100000],a[100000],lim;   
 
void generare()
 {
     int k,i;
     float rad;
     long double m1;
     memset(pr,0,sizeof(pr));
     m1=p;
     rad=int(sqrt(m1));
     for (i=2; i<=rad+2; i++)
      {
       k=i*i;
       while (k<=rad+2)
	    {
	     pr[k]=1;
	     k+=i;
    	}
      }
      k=1;
     for (i=2; i<=rad+1; i++)
       if (pr[i]==0) a[k++]=i;
     lim=k-1;
  }

void descompune()
 {
    int vl,i,j;
    ll m1;
    memset(d,0,sizeof(d));
    j=0;
    i=1;
    m1=p;
    while (m1!=1 && i<=lim)
     if (m1%a[i]==0)
     {
       vl=0;
       while (m1%a[i]==0)
	    { vl++; m1/=a[i]; }
       j++;
       d[j].n=a[i];
       d[j].p=vl;
     }  else i++;
   if (m1!=1) { d[++j].n=m1; d[j].p=1; }
   m=j;
   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);
    generare();
    
    descompune();
    cautafact();
    
    fclose(fin); fclose(fout);
    
    return 0;
    
}