#include <cstdio> 
 
using namespace std; 

long long P; 

long long put (long long x,long long y) 
{ 
	long long rez = 0; 
	while (x) 
	{ 
		rez += x / y; 
		x /= y; 
	} 
	return rez; 
} 
 
 
long long BS (long long p,long long pr) 
{ 
	long long i, pas = 1 << 30; 
	for (i = 0; pas; pas >>= 1) 
	{ 
	if (put(i + pas,p) < pr) 
		{ 
			i += pas; 
		} 
	} 
	return i + 1; 
} 
 
 
int main () 
{ 
	freopen ("gfact.in", "r", stdin); 
	freopen ("gfact.out", "w", stdout); 
	long long p,q,x,prim[20],pu[20],cont,i;
	scanf ("%lld %lld", &p, &q);
	x=p;
	long long max=0;
	cont=0;
	for(i=2;i<=x;i++)
	{
		if (x%i==0)
		{
			cont++;
			prim[cont]=i;
			pu[cont]=0;
			while (x%i==0)
			{
				x=x/i;
				pu[cont]++;
			}
			pu[cont]*=q;
		}
	}
	for (i=1;i<=cont;i++)
	{
		long long x;
		x=BS(prim[cont],pu[cont]);
		if (x>max) 
			max=x;
	}
	printf("%lld",max);
return 0; 
}