#include<stdio.h>
#include<math.h>
#define LL long long
#define max(x,y) (x>y) ? x : y
using namespace std;
LL factors[2012],powers[2012];	

void desc(int n)
{
LL d=2,e,limita;
limita=(LL)sqrt(n);
while(d<=limita && n>1)
{
	e=0;
	while((n%d)==0)
	{
		e++;
		n/=d;
	}
	if(e)
		{
			factors[++factors[0]]=d;
			powers[++powers[0]]=e;
	
		}
	d++;
}
if(n>1)
	{
		factors[++factors[0]]=n; 
		powers[++powers[0]]=1;
    }
}

long long multi(long long a,long long b)
{
long long num=b,s=0;	
while(a/num)
{
	s+=a/num;
	num*=b;
}
return s;
}

LL cautare(LL fact,LL exp)
{
	LL pozdy=0,elfus,med,st=1,dr=(1ll<<61)-1;
	while(st<=dr)
	{
		med=(st+dr)>>1;
		elfus=multi(fact,med);
		if(elfus>=exp)
		{
			dr=med-1;
			pozdy=med;
		}
		else
			st=med+1;
	}
	return pozdy;
}

int main()
{
	LL p,q,sol=-1,i;
	
	freopen("gfact.in","r",stdin);
	freopen("gfact.out","w",stdout);
	
	scanf("%lld%lld",&p,&q);
	desc(p); //factors vs powers
	
	for(i=1;i<=powers[0];i++)
		powers[i]*=q;
	
	for(i=1;i<=powers[0];i++)
		sol=max(sol,cautare(factors[i],powers[i]));
	printf("%lld",sol);
	return 0;
}