#include <stdio.h>
#include <limits.h>

#define pr(x) fprintf (stderr,"%d ",x)

long long p, q;


inline long long max (long long a, long long b)
{
	if (a > b)
		return a;
	return b;
}

long long mult (long long fact, long long w)
{
	long long s;
	long long p;
	for (s=0, p=fact; w >= p && p > 0; p*=fact)
		s+=w/p;
	return s;
}

long long binary_search (long long d, long long p)
{
	long long st=1, dr=LLONG_MAX, m;
	while (st < dr)
	{
		//m=(st+dr) >> 1;
		//pr (st);
		//pr (dr);
		//pr ((double)st/2+(double)dr/2);
		m=(long double)st/2+(long double)dr/2;
		//pr (m);
		if (mult (d, m) >= p)
			dr=m;
		else
			st=m+1;
	}
	return st;
}

long long descomp ()
{
	long long d, num, n=0;
	for (d=2; d*d <= p; ++d)
		if (p % d == 0)	
		{
			num=0;
			while (p % d == 0)
			{
				++num;
				p/=d;
			}
			n=max (n, binary_search (d, num*q));
		}
	if (p > 1)
		n=max (n, binary_search (p, q));
	return n;
}

int main ()
{
	freopen ("gfact.in", "r", stdin);
	freopen ("gfact.out", "w", stdout);
	scanf ("%lld%lld", &p, &q);
	printf ("%lld\n", descomp ());
	return 0;
}