#include <cstdio>

#define file_in "frac.in"
#define file_out "frac.out"

long long n,p;
long long q[1000],nr;

void citire()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%lld %lld", &n, &p);
}	

long long verif(long long x)
{
	long long sol=x,i,prod,nrr,j;

	for(i=1;i<(1LL<<nr);++i)
	{
		nrr=0;
		prod=1;

		for(j=1;j<=nr;++j)
			if(i&(1LL<<(j-1)))
			{
				++nrr,
				prod*=q[j];
			}
		if (nrr&1) 
			sol-=(x/prod);
		else
			sol+=(x/prod);
	}

	return sol;
}


void solve()
{

	long long i;
	nr=0;
	for (i=2;i*i<=n;++i)
		if (n%i==0)
		{
			q[++nr]=i;
			while (n%i==0)
				n/=i;
		}
	if (n>1)
		q[++nr]=n;

	
	long long step=1LL<<62;
	
	for (i=step;step;step>>=1)
		 if (i+step>0 && verif(i-step)>=p)
			  i-=step;
	
	printf("%lld\n", i);
}

int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}