#include<cstdio>
using namespace std;


long long p,n,d[11],nrd;


void descompune(long long n)
{
	long long i;
	for(i=2;i*i<=n;++i)
		if (n%i==0)
		{
			n/=i;
			d[nrd++]=i;
			while(n%i==0)
				n/=i;
		}
	if (n!=1)
		d[nrd++]=n;
}

long long f(long long x)
{
	long long r=0;
	long long i,j,p,par;
	for(i=0;i<((long long)1<<nrd); ++i)
	{
		par=1;
		p=1;
		for(j=0;j<nrd;++j)
			if((i & (1<<j))!=0)
			{
				p*=d[j];
				par*=-1;
			}
			r+=x/(par*p);
	}
	return r;
}

long long caut()
{
	long long i,pas=(long long)1<<60;
// 	printf("%lld\n",pas);
	for(i=0;pas;pas>>=1)
	{
		//printf("%lld %lld\n",i,pas);
		if (f(i+pas)<p)
			i+=pas;
	}
	return i+1;
	
}


int main()
{
	freopen("frac.in","r",stdin);
	//freopen("frac.out","w",stdout);
	scanf("%lld%lld",&n,&p);
	descompune(n);
	printf("%lld",caut());
}