#include<cstdio>

long long n,p,nrp,d[1000],produs[1000];

void citire()
{
	scanf("%lld%lld",&n,&p);
}

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

void rez()
{
	long long i,j,p,q,max=1<<nrp;
	for (i=0;i<max;++i)
	{
		p=1;
		q=i;
		for (j=0;q;++j,q>>=1)
			if (q%2==1)
				p*=-d[j];
		produs[i]=p;
	}	
}

long long functie(long long x)
{
	long long s=0;
	int max=1<<nrp,i;
	for (i=0;i<max;++i)
		s+=x/produs[i];
	return s;	
}

void cautbin()
{
	long long i=0,pas=(long long)1<<61;
	for (i=0;pas;pas>>=1)
		if (functie(i+pas)<p)
			i+=pas;
	printf("%lld\n",++i);
}

int main()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	citire();
	desc();
	rez();
	cautbin();
	return 0;
}