#include <cstdio>

const int MAX_L = 1000;

long long n, p, z;
long long sol;
long long f[MAX_L];

long long check(long long x)
{
	long long ret = x;
	for (long long i = 1; i < (1 << z); ++i)
	{
		long long y = 1;
		long long q = 1;
		
		for (int j = 0; j < z; ++j)
			if (i & (1 << j))
			{
				y *= f[j];
				q *= -1;
			}
		
		ret += q * (x / y);
	}
	
	return ret;
}

void bin(long long st, long long dr)
{
	while (st < dr)
	{
		long long mij = st + (dr - st) / 2;
		if (check(mij) >= p) dr = mij;
		else st = mij + 1;
	}
	
	sol = st;
}

int main()
{
	long long i;
	freopen("frac.in", "r", stdin);
	freopen("frac.out", "w", stdout);
	
	scanf("%lld %lld", &n, &p);
	
	long long m = n;
	for (i = 2; i * i <= m; ++i)
	{
		if (m % i == 0) f[z++] = i;
		for (; m % i == 0; m /= i);
	}
	
	if (m) f[z++] = m;
	
	bin(1, (long long)1 << 61);
	
	printf("%lld\n", sol);
}