#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

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

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

long long p,q,fc,d,ct[505000],st,dr,mj,rez,factor[55000],nr[55000],mx;
long long k,i;

int calc(int vl,int k)
{	
	int mult=1,x=0,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
	int ct2=0;
	while(fc>1 && ct2==0)
	{	
		
		if(fc%d==0)
		{
			if(d>sqrt(p))
				ct2++;
			fc=fc/d;
			if(ct[d]==0)
				factor[++k]=d;
			ct[d]++;
		}
		else
			d++;
	}
	
	
	
	for(i=1;i<=k;i++)
	{	
		st=1; 
		if(ct[factor[i]]*q%2==0)
			dr=ct[factor[i]]*q+4;
		else
			dr=ct[factor[i]]*q+1;
		mj=0,rez=0;
		while(st<dr)
		{
			mj=(st+dr)/2;
			rez=calc(mj*factor[i],i);
			if(rez>ct[factor[i]]*q)
				dr=mj;
			else
				if(rez<ct[factor[i]]*q)
				st=mj+1;
			else
				break;
		}
		int c1=mj*factor[i];
		int c2=mj*factor[i]-1;
		nr[i]=c1;
		while(calc(c1,i)==calc(c2,i))
		{	
			nr[i]=c1;
			c1=c2;
			c2--;
		}
		
	}
		
	for(i=1;i<=k;i++)
		if(nr[i]>mx)
			mx=nr[i];
	fout<<mx<<"\n";
	return 0;
}