#include<fstream.h>
ifstream f("gfact.in");
ofstream g("gfact.out");


int nr[50],put[50],p,q,n=0;

int nr_de_peuri(long x,int p)
{
  long k=x;
  int tz=0;

  while(k%p==0)
   {
    tz++;
    k=k/p;
   }
  return tz;
}

int nextprim (int tz)
{
 int tzz=0;
 while (tzz==0)
 {
  tz++;    tzz=1;
  for (int j=2;j<=(tz/2);j++) if (tz % j == 0) tzz=0;
 }
 return tz;
}


void descompunere (int pp, int qq)
{
  int j=2;
  while (pp>1)
   {
    while (pp%j==0)
	{
	pp=pp/j;
	put[n]+=qq;
	nr[n]=j;
	}
    if (nr[n]) n++;
    j=nextprim(j);
   }
}

int numar(int x)
{
int tz=0,m=0;
while (m<put[x])
 {
 tz+=nr[x];
 m+=nr_de_peuri(tz,nr[x]);
 }

return tz;
}

int main()
{
f>>p>>q;
int m=0;
long i=0;


descompunere(p,q);
int max=0,aux;
for (i=0;i<n;i++) { aux=numar(i);
		    if (aux>max) max=aux;
		  }
g<<max;
f.close();
g.close();
}