#include <stdio.h>
long long prim[15],nrp=1,n,p;
void citire()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	scanf("%lld%lld",&n,&p);
}
void descomp(int q)
{
	int d,q1;
	for (d=2; d*d<=q; d++)
	{
		q1=q;
		while (q%d==0)
		{
			prim[nrp]=d;
			q/=d;
		}
		if (q1!=q)
		nrp++;
	}
	if (q>1)
		prim[nrp++]=q;
	nrp--;
}
void calcul(long long x,long long &nrbiti,long long &prod)
{
	long long j;
	prod=1; nrbiti=0;
	for (j=1; j<=nrp; ++j,x>>=1)
		if (x&1)
		{
			prod*=prim[j];
			nrbiti++;
		}
}
long long f(long long x)
{
	long long i,s=x,nb,pr;
	for (i=1; i<(1<<nrp); ++i)
	{
		calcul(i,nb,pr);
		if (nb%2)
			s-=x/pr;
		else
			s+=x/pr;
	}
	return s;
}
void rez()
{
	long long st=1,dr=(long long)1<<(long long)61;
	long long m;
	while (st!=dr)
	{
		m=(st+dr)/2;
		if (f(m)>=p)
			dr=m;
		else
			st=m+1;
	}
	printf("%lld\n",st);
}

int main()
{
	citire();
	descomp(n);
	rez();
}