#include <bits/stdc++.h>
#define ll long long 

using namespace std;

ifstream in("frac.in");
ofstream out("frac.out");

ll n, p, stk[20], vf, st, dr, mid;
bitset <110100> viz;

bool check(ll num) {
	ll ans = 0;
	for (int mask = 1; mask < (1 << vf); mask++) {
		int cnt = 0;
		ll val = 1;
		for (int bit = 0; bit < vf; bit++)
			if (mask & (1 << bit)) {
				val *= stk[bit];
				cnt++;
			}
		if (cnt & 1)
			ans += num / val;
		else ans -= num / val; 
	}
	return (num - ans >= p);
}

int main() {
	in >> n >> p;
	for (ll i = 2; i * i <= n; i++) {
		int cnt = 0;
		while (n % i == 0) {
			cnt++;
			n /= i;
		}
		if (cnt)
			stk[vf++] = i;
	}
	if (n > 1)
		stk[vf++] = n;
	st = 1LL;
	dr = (1LL << 61);
	while (st <= dr) {
		mid = st + dr >> 1LL;
		if (check(mid))
			dr = mid - 1LL;
		else st = mid + 1LL;
	}
	out << st;
	return 0;
}