#include <stdio.h>
const int n_max = 20;
long long i, n, k, s, x, st, dr;
long long d[n_max];
void inc_exc()
{
	int i, j;
	long long p = 0, o = 0, nr = 0;
	s = 0;
	for (i = 1; i < 1<<d[0]; ++ i)
	{
		o = 1;
		nr = 0;
		for (j = 0; (1<<j) <= i; ++ j)
		if (((1<<j)& i) > 0)
		{
			o *= d[j+1];
			++nr;
		}
		p = x/o;
		if (nr%2 == 1)
			s += p;
		else
			s -= p;
	}
}
			


int main()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	scanf("%lld %lld", &n, &k);
	st = 1; dr = (long long)1<<61;
	for (i = 2; i * i <= n; ++ i)
	{
		if (n%i == 0)
		{
			d[++d[0]] = i;
			while (n%i == 0)
				n/=i;
		}
	}
	if (n > 1) d[++d[0]] = n;
	//Gasirea divizorilor
	while (st < dr-1 )
	{
		x = (st+dr)/2;
		s = 0;
		inc_exc();
		if (x-s < k)
			st = x;
		else
			dr = x;
	}
	s = 0;
	x = st;
	inc_exc();
	if (x-s  == k)
		printf("%lld\n", st);
	else
		printf("%lld\n", dr);
	return 0;
}