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

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

int p, q;


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

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

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

int descomp ()
{
	int 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 ("%d%d", &p, &q);
	printf ("%d\n", descomp ());
	return 0;
}