#include <cstdio>

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

long long n,p;
int 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)
{
	int i,j;
	long long sol=x;
	long long prod;
	int nrr=0;
	
	for (i=0;i<(1<<nr);++i)
	{
		nrr=0;
		prod=1;
		for (j=1;j<=nr;++j)
			 if (i&(1<<(j-1)))
			 {
				 nrr++;
				 prod*=q[j];
			 }
			 if (nrr&1)
				  sol-=x/prod;
			 else
				 sol+=x/prod;
	}
	
	return sol;
}

void solve()
{
	int j;
	long long i,ls,ld,mij,sol;
	
	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;

	/*ls=0;
    ld=100;
	while(ls<=ld)
	{
		mij=(ls+ld)>>1;
		if (verif(mij)>=p)
		{
			sol=mij;
			ld=mij-1;
		}
		else
			ls=mij+1;
	}*/
	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;
	
}