#include <stdio.h>
long long n, p;
int prim[20];

void desc (long long x)
{
	long long i;
	
	for (i = 2; i * i <= x; i ++)
	{
		prim[++ prim[0]] = i;
		
		while (x % i == 0)
			x /= i;
	}
	
	if (x > 1)
		prim[++ prim[0]] = x;
}

long long fractii (long long x)
{
	int i, j, b, lim = (1 << prim[0]) - 1;
	long long nr = 0, p;
	
	for (i = 0; i <= lim; i ++)
	{
		b = 0;
		p = 1;
		
		for (j = 1; j <= prim[0]; j ++)
			if (i & (1 << j - 1))
			{
				b ++;
				p = p * prim[j];
			}
		
		nr = nr + x / p * (b & 1 ? -1 : 1);
	}
	
	return nr;
}

int main ()
{
	freopen ("frac.in", "r", stdin);
	freopen ("frac.out", "w", stdout);
	scanf ("%lld %lld\n", &n, &p);
	desc (n);
	
	long long st = 0, dr = 1LL << 61, m, sol;
	
	while (st <= dr)
	{
		m = (st + dr) >> 1;
		if (fractii (m) >= p)
		{
			sol = m;
			dr = m - 1;
		}
		else
			st = m + 1;
	}
	
	printf ("%d\n", sol);
	return 0;
}