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

void caut(long long a,long long x)
{
	long long i,pas=(long long)1<<60;
	for (i=0;pas;pas>>=1)
		if (putere(i+pas,a)<x) i+=pas;
	if (maxim<i+1) maxim=i+1;
}

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

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