#include<fstream>
using namespace std;
int maxim,p,q;
int putere(int n,int p)
{
	int rez=0;
	while (n)
	{
		rez+=n/p;
		n/=p;
	}
	return rez;
}

void caut(int p,int x)
{
	int i,pas=1<<30;
	for (i=0;pas;pas>>=1)
		if (putere(i+pas,p)<x) i+=pas;
	if (maxim<i+1) maxim=i+1;
}

void gfact()
{
	int p2,i;
	for (i=2;i*i<=p;i++)
		if (p%i==0) 
		{
			p2=0;
			while(p%i==0)
			{
				p/=i;
				++p2;
			}
			p2*=q;
			caut(i,p2);			
		}
	if(p!=1) caut(i,q);
}

int main()
{
	ifstream f("gfact.in");
	ofstream o("gfact.out");
	f>>p>>q;
	gfact();
	o<<maxim;
	return 0;
}