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


int p, q;


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

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

int binary_search (int d, int p)
{
	int st=1, dr=INT_MAX, m, x;
	while (st < dr)
	{
		m=(st+dr) >> 1;
		x=mult (d, m);
		if (x >= 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;
}