#include <stdio.h>

long long n, p, o, prim [35];


void fact (int n)
{
	int div=2;
	while (n > 1)
	{
		if (n % div == 0)
		{
			n/=div;
			prim [++prim [0]]=div;
		}
		while (n % div == 0)
			n/=div;
		++div;
	}
	o=(1<<prim [0]);
}

void calcul (long long w, int &nrbiti, long long &prod)
{
	int i;
	nrbiti=0;
	prod=1;
	for (i=0; i<=prim [0]; ++i)
		if (w&(1 << i))
			{
				++nrbiti;
				prod*=prim [i];
			}
}

long long f(long long x)
{
	long long i, s=x, prod;
	int nrbiti;
	for (i=1; i<=o; ++i)
	{
			calcul (i, nrbiti, prod);
			if (nrbiti & 1)//nrbiti impar
				s+=x/prod;
			else
				s-=x/prod;
	}
	return s;
}

long long caut (long long st, long long dr)
{
	long long mij;
	while (st <= dr)
	{
		mij=(st+dr)>>1;
		if (f (mij) <= p)
			st=mij+1;
		else
			dr=mij;
	}
	return st;
}

int main ()
{
	freopen ("frac.in", "r", stdin);
	freopen ("frac.out", "w", stdout);
	scanf ("%d%d", &n, &p);
	fact (n);
	printf ("%lld", caut (1, ((long long)1<<(long long)5)));
	return 0;
}