#include<stdio.h>

int p,q,putere,x[31],y[31];

int desc(int &n,int k)
{
	int nr=0;
	while(n%k==0)
	{
		n/=k;
		++nr;
	}
	return nr;
}

int fact(int n,int p)//gaseste cel mai mic k cu k! divizibil cu n la p
{
	int x[30],y[30],k=0,m=0;
	x[++m]=n;
	y[m]=1;
	while(x[m]*n<=2000000000 && x[m]<p)
	{
		x[m+1] = n * x[m];
		y[m+1] = x[m] + y[m];
		++m;
	}
	while(p)
	{
		k+=p/y[m]*x[m];
		p%=y[m--];
	}
	return k;
}

int calcul()
{
	int r,max=0,putere;
	for(int i=2;i*i<=p;++i)
		if(p%i==0)
		{
			putere=desc(p,i);//returneaza puterea la care apare i in desc lui p si-l modifica pe p
			r=fact(i,putere*q);//caut cel mai mic n cu propr ca n! se imparte exact la i la putere*q
			if(r>max)
				max=r;
		}
	if(p!=1)
	{
		r=fact(p,q);
		if(r>max)
			max=r;
	}
	return max;
}
int main()
{
	freopen("gfact.in","r",stdin);
	freopen("gfact.out","w",stdout);
	scanf("%d%d",&p,&q);
	printf("%d\n",calcul());
	return 0;
}