#include<cstdio>
using namespace std;
int exp(int p,int n)
{
	///p in n!
	int nr=0;
	while(n)
	{
		nr=nr+n/p;
		n=n/p;
		}
		return nr;
}
long long bs(int p, int q)
{
	int st,dr,med,last;
	st=1;
	dr=((1LL<<31)-1);
	while(st<=dr)
	{
		med=st+((dr-st)>>1);
		if(exp(p,med)>=q)
		{
			dr=med-1;
			last=med;
		}
		else
				st=med+1;
	}
	return last;
}
int main()
{
	freopen("gfact.in","r",stdin);
	freopen("gfact.out","w",stdout);
	int n,p,e,q,mmax=0,nr,d;
	scanf("%d%d",&p,&q);
	d=2;
	while(p>1 && 1LL * d*d<=p)
	{
		e=0;
		while(p%d==0)
		{
			p=p/d;
			e++;
		}
		if(e!=0)
		{
			e=e*q;
			nr=bs(d,e);
			if(nr>mmax)
				mmax=nr;
		}
		d++;
	}
	if(p>1)
	{
		e=q;
		nr=bs(p,e);
		if(nr>mmax)
			mmax=nr;
	}
	printf("%d",mmax);
}