#include<stdio.h>
long long n,p,nrp,prim[1<<4],prod[1<<10];
void pinex()
{
	long long i,j,x,p;
	for(i=0 ; i<(1<<nrp) ; ++i)
	{
		p=1;
		x=i;
		for(j=0 ; x ; ++j,x>>=1) if(x&1) p *= -prim[j];
		prod[i]=p;
	}
}
long long calc(long long x)
{
	int i;
	long long s=0;
	for(i=0;i<(1<<nrp);++i)
		s+=x/prod[i];
	return s;
}
int main()
{
	long long i,pas=(long long)1<<61;
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	scanf("%lld%lld",&n,&p);
	for(i=2;i*i<=n;++i)
		if(n%i==0)
		{
			while(n%i==0) n/=i;
			prim[nrp++]=i;
		}
	if(n!=1) prim[nrp++]=n;
	pinex();
	for(i=0 ; pas ; pas>>=1) if(calc(i+pas)<p) i+=pas;
	printf("%lld\n",++i);
	return 0;
}