#include <cstdio>
#include <iostream>
#define INF "gfact.in"
#define OUF "gfact.out"
#define NMAX 2048
using namespace std;

inline long long prim(long long nr2)
{
	long long  div,ok;
	ok=1;div=2;
	while(div*div<=nr2&&ok)
	{
		if(nr2%div==0) ok=0;
		++div;
	}
	return ok;
}

inline void fact(long long f[],long long p[],long long &dim,long long nr)
{
	long long mem,k,i;
	i=0;k=2;mem=nr;
	while(k*k<=nr)
	{
		if(mem%k==0)
		{
			++i;f[i]=k;
			while(mem%k==0&&mem)
			{
				mem/=k;
				++p[i];
			}
		}
		++k;
	}
	if(mem>1) { ++i;f[i]=mem;p[i]=1; }
	dim=i;
}

inline long long xpfact(long long x,long long fact)
{
	long long k,pwr=0;
	k=x;
	while(k<=fact)
	{
		pwr+=fact/k;
		k*=x;
	}
	return pwr;
}

int main()
{
	FILE *in,*out;
	long long i,ft[NMAX],pt[NMAX]={0},dim=0;
	long long st,dr,mij,p,q,b,xp,alfa;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	fscanf(in,"%lld%lld",&p,&q);
	fact(ft,pt,dim,p);
	for(i=1;i<=dim;++i) pt[i]*=q;
	b=0;
	for(i=1;i<=dim;++i)
	{
		st=1;dr=p*q;alfa=dr;
//		cout<<ft[i]<< ' '<<st<<' '<<dr<<endl;
		while(st<=dr)
		{
			mij=(st+dr)/2;
			xp=xpfact(ft[i],mij);
//			cout<<mij<<' '<<xp<<endl;
		        if(xp>=pt[i]&&mij<alfa) alfa=mij;
			if(xp<pt[i]) st=mij+1;
			else dr=mij-1;
		}
//		cout<<endl<<endl<<endl<<endl<<alfa<< ' ' <<xpfact(ft[i],alfa)<<endl;
		if(alfa>b) b=alfa;
	}

	fprintf(out,"%lld\n",b);
	fclose(in);fclose(out);
	return 0;
}