#include<fstream>
#define NMAX 50

using namespace std;

ifstream f("gfact.in");
ofstream g("gfact.out");

int p, q, e[NMAX], put[NMAX], n=0;

void Citeste()
{
	f>>p>>q;
}

void Descompune()
{
	int d=2;
	
	if (p%d==0)
	{
		e[++n]=d;
		while (p%d==0)
			++put[n], p/=d;
	}
	
	d=3;
	while (d*d<=p)
	{
		if (p%d==0)
		{
			e[++n]=d;
			while (p%d==0)
				++put[n], p/=d;
		}
		d+=2;
	}
	
	if (p!=1) e[++n]=p, put[n]=1;
}

int putere(int x, int y, long long z)
{
	long long nr=0, t=x;
	
	while (z/t>0) nr+=z/t, t*=(long long)x;
	
	if (nr>=y) return 1;
	return 0;
}

void Cautare()
{
	long long st=1, dr=-1, mij, mx=-1, nr;
	int i;
	
	for (i=1; i<=n; ++i)
		put[i]*=q;
	
	for (i=1; i<=n; ++i)
	{
		st=1; dr=(long long)e[i]*(long long)put[i];
		while (st<=dr && st!=mij)
		{
			mij=(st+dr)/2;
			if ( putere(e[i], put[i], mij) ) dr=mij-1;
			else nr=mij,st=mij+1;
		}
		if (nr>mx)mx=nr;
	}
	g<<mx+1<<"\n";
}

int main()
{
	Citeste();
	
	Descompune();
	
	Cautare();
	
	f.close();
	g.close();
	return 0;
}