#include <stdio.h>
#include <algorithm>
#include <math.h>
#define ll long long

using namespace std;

ll n, k, r;
ll div_p[128];

ll verif(ll m)
{
	ll rez = 0;
	for (int i = 1; i < (1 << r); i++)
	{
		ll nr1 = 0, val = 1, st = 1;
		for (int j = i, id = 1; j; j /= 2, id++)
		{
			nr1 += (j & 1);
			if (j & 1)
				val *= div_p[id];
		}
		if (!(nr1 & 1))
			st = -1;
		rez = rez + st * (m / val);
	}
	return rez;
}

ll cauta(ll p, ll u)
{
	ll m = (p + u) / 2;
	ll prec = m - verif(m), vp = m - 1 - verif(m - 1);
	if (prec == k && vp < k)
		return m;
	if (prec < k)
		return cauta(m + 1, u);
	else return cauta(p, m - 1);
}

int main()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	scanf("%lld %lld", &n, &k);
	for (int i = 2; i <= sqrt( (double) n); i++)
		if (!(n % i))
		{
			div_p[++r] = i;
			while (!(n % i))
				n /= i;
		}
	if (n > 1)
		div_p[++r] = n;
	ll valmax = 1;
	for (int i = 1; i < 62; i++)
		valmax *= 2;
	ll x = cauta(1, valmax);
	printf("%lld", x);
	fclose(stdin);
	fclose(stdout);
	return 0;
}