#include <iostream>
#include <fstream>

using namespace std;

const char iname[] = "gfact.in";
const char oname[] = "gfact.out";

ifstream fin(iname);
ofstream fout(oname);

int p,q,fc,d,ct[45000],st,dr,mj,rez,factor[45000],nr[45000],mx;
int k,i;

int calc(int vl,int k)
{	
	int mult,x,nom=0,sm=0;
	mult=factor[k];
	x=vl;
	if(factor[k]>0)
		while(x>=mult)
			{
				nom=x/mult;
				mult*=factor[k];
				sm+=nom;
			}
	return sm;
}

		
int main()
{
	fin>>p>>q;
	fc=p,d=2;
	//factorizam p si numar
	while(fc>1)
	{
		if(fc%d==0)
		{
			fc=fc/d;
			if(ct[d]==0)
				factor[++k]=d;
			ct[d]++;
		}
		else
			d++;
	}
	
	
	
	for(i=1;i<=k;i++)
	{	
		st=2;
		dr=2000;
		mj=0,rez=0;
		while(st<dr)
		{
			mj=(st+dr)/2;
			rez=calc(mj,i);
			if(rez>ct[factor[i]]*q)
				dr=mj;
			else
				if(rez<ct[factor[i]]*q)
				st=mj+1;
			else
				break;
		}
		if(calc(mj,i)==calc(mj-1,i))
			while(calc(mj,i)==calc(mj-1,i))
				mj--;
		else
			while(calc(mj,i)==calc(mj+1,i))
				mj++;
			
		nr[i]=mj;
	}
		
	for(i=1;i<=k;i++)
		if(nr[i]>mx)
			mx=nr[i];
	fout<<mx<<"\n";
	return 0;
}