#include <fstream>
#include <cmath>

using namespace std;

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

const long long INF = 0x4000000000000000;
const int NMAX = 1000000;
const int P_MAX = 200000;

long long p[P_MAX + 1];   ///  Tin divizorii primi ai lui Y
bool ciur[NMAX + 3];
long long pr[P_MAX + 1], pr_count = 0;  ///  Tin numerele prime

void ciurul() {
	long long lim = 1000;
	for (int i = 4; i <= NMAX; i += 2) ciur[i] = 1;
	for (int i = 3; i <= lim; i += 2) {
		if (!ciur[i]) {
			for (int j = i*i; j <= NMAX; j += 2 * i) ciur[j] = 1;
		}
	}
	pr[++pr_count] = 2;
	for (int i = 3; i <= NMAX; i += 2) {
		if (!ciur[i])  pr[++pr_count] = i;
	}
}

long long Desc_factori(long long N) {
	long long R = 0, ind = 1;
	long long lim = (long long)sqrt(1.0*N);
	bool ok = 0;
	while (N>1 && pr[ind] <= lim) {
		ok = 0;
		while (N%pr[ind] == 0) {
			N /= pr[ind];
			ok = 1;
		}
		if (ok) {
			p[++R] = pr[ind];
			lim = (long long)sqrt(1.0*N);
		}
		++ind;
	}
	if (N>1) p[++R] = N;
	return R;
}


long long PINEX(long long X, long long Y) {
	long long Sol = 0;
	long long nr = Desc_factori(Y);
	long long k = 1 << nr;
	for (long long i = 1; i<k; ++i) {
		long long cnt = 0, prod = 1;
		for (long long j = 0; j<nr; ++j) {
			if (i & (1 << j)) {
				++cnt;
				prod *= p[j + 1];
			}
		}
		if (cnt % 2 == 1) {   ///  Adun divizorii
			Sol += X / prod;
		}
		else {               ///  Scad divizorii
			Sol -= X / prod;
		}
	}
	return X - Sol;
}

int main() {
	ciurul();
	long long Y, P;
	in >> Y >> P;
	///  Caut binar
	long long step = INF;
	int i = 0;
	for (; step; step >>= 1) {
		if (PINEX(i + step, Y) < P) i += step;
	}
	out << i + 1 << '\n';
	return 0;
}