#include <cstdio>
#include <vector>
using namespace std;

long long n,p;
vector<int> pd;

bool cmp ( long long n ) {
	long long tot = n;
	for (int stare = 1; stare < (1 << pd.size()); ++stare) {
		long long prod = 1;
		int semn = 0;
		for (int i = 0; i < pd.size(); ++i) {
			if (stare & (1 << i)) {
				prod *= pd[i];
				++semn;
			}
		}
		semn = (semn%2 == 0) ? 1 : -1;
		tot += semn*(n/prod);
	}
	return tot >= p;
}

long long bs() {
	long long s, d;
	for (s = 0, d = (long long)1 << 61; d - s > 1; ) {
		long long m = (s+d)/2;
		if (cmp(m))
			d = m; else
			s = m;
	}
	if (cmp(s))
		return s; else
		return d;
}

int main() {
	freopen("frac.in","rt",stdin);
	freopen("frac.out","wt",stdout);
	scanf("%lld %lld",&n,&p);
	
	int nv = n;
	for (int i = 2; i*i < n; ++i) {
		if (n % i == 0) {
			pd.push_back(i);
			for (; n % i == 0; n /= i);
		}
	}
	if (n) pd.push_back(n);
	n = nv;

	printf("%lld\n",bs());
	return 0;
}