#include <stdio.h>
#include <math.h>
#include <string.h>

long long sel[16], v[16], n, k, nr;

long long ver(long long a) {
	long long s = 0,i;
	memset(sel, 0, sizeof(sel));
	while (sel[0] == 0) {
		for (i = nr; i >= 0; --i) {
			if (sel[i] == 0) {
				sel[i] = 1;
				break;
			} else {
				sel[i] = 0;
			}
		}
		long long p = 1 ,t = 0;
		for (i = nr; i >= 1; --i) {
			if (sel[i]) {
				p *= v[i];
				t = !t;
			}
		}
		if (p == 1) {
			break;
		}
		if (t == 0) {
			s -= a / p;			
		} else {
			s += a / p;
		}
	}
	return a - s;
}

long long cauta(long long a, long long b) {
	long long c;
	if (a == b) {
		return a;
	}
	c = (a + b) / 2;
	if (ver(c) >= k) {
		return cauta(a, c);
	}
	return cauta(c + 1, b);
}

void descompune() {
	long long i;
	for (i = 2; i * i <= n; ++i) {
		if (n % i == 0) {
			v[++nr] = i;
			while (n % i == 0) {
				n /= i;
			}
		}
	}
	if (n != 0) {
		v[++nr] = n;
	}
}

int main() {
	freopen("frac.in", "r", stdin);
	freopen("frac.out", "w", stdout);
	scanf("%lld%lld", &n, &k);
	descompune();
	long long max = 1024 * 1024 * 1024;
	max = max * max * 2;
	printf("%lld\n", cauta(0, max));
	return 0;
}