#include <stdio.h>

long long n, p, sum, prod = 1, nr = 0;
int prim[20000], v[128];

void go(int pos, long long x)
{
	if (prod > x)
		return;

	if (pos > v[0]) {
		if (nr > 0) {
			if (nr % 2)
				sum -= x / prod;
			else
				sum += x / prod;
		}
	} else {
		go(pos + 1, x);
		prod = (long long)prod * v[pos];
		++nr;
		go(pos + 1, x);
		--nr;
		prod = (long long)prod / v[pos];
	}
}

long long solve(long long x)
{
	sum = x;

	go(1, x);

	return sum;
}

int main()
{
	freopen("frac.in", "r", stdin);
	freopen("frac.out", "w", stdout);

	scanf("%lld %lld", &n, &p);

	for (int i = 2; i <= 150000; ++i) {
		int ok = 1;

		for (int j = 1; j <= prim[0] && prim[j] * prim[j] <= i && ok; ++j)
			if (i % prim[j] == 0)
				ok = 0;

		if (ok)
			prim[++prim[0]] = i;
	}

	int tmp = n;

	for (int i = 1; (long long)prim[i] * prim[i] <= n; ++i)
		if (tmp % prim[i] == 0) {
			v[++v[0]] = prim[i];

			while (tmp % prim[i] == 0)
				tmp = (long long)tmp / prim[i];
		}

	if (tmp > 1)
		v[++v[0]] = tmp;

	long long step = (long long)1 << 61, crt;

	for (crt = 0; step; step /= 2)
		if (solve((long long)crt + step) < p)
			crt = (long long)crt + step;

	printf("%lld\n", (long long)crt + 1);

	return 0;
}