#include <stdio.h>

#define Nmax 1000001

int a,p,q,cont,d[2][Nmax],b[Nmax];

void afla(int p)
{
    int i;
    for(i=2;i*i<=p;++i)
        {
            if(p%i==0)
                {
                    ++cont;
                    d[0][cont]=i;
                    while(p%i==0)
                        {
                            ++d[1][cont];
                            p/=i;
                        }
                    d[i][cont]=d[i][cont]*q;
                }
        }    
    if(p>1)
        {
                ++cont;
                d[0][cont]=p;
                d[1][cont]=q;
        }
}

int putere(int x,int t)
{
	int s=0,y=t;
	while(x>=t)
		{
			s+=x/t;
			x/=y;
		}
	return s;
}

int cauta(int st,int dr,int nr)
{
	if(st==dr)
		return st;
	else
		{
		   int mid=(st+dr)/2;
		   int bi=mid;//*d[0][nr];
		   if(putere(bi,d[0][nr])>=d[1][nr])
				return cauta(st,mid,nr);
			else
				return cauta(mid+1,dr,nr);
		}
}

int main()
{
	freopen("gfact.in","r",stdin);
	freopen("gfact.out","w",stdout);
	scanf("%d%d",&p,&q);
	afla(p);

	int i;

	for(i=1;i<=cont;++i)
		{
			b[i]=cauta(1,d[1][i]*d[0][i],i);
		}
	int max=0;
	for(i=1;i<=cont;++i)
		{
			if(b[i]>max)
				max=b[i];
		}
	printf("%d",max);
	return 0;
}