#include<fstream>

using namespace std;

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

const long long inf = 1LL << 61;
const int ArraySize = 128;

long long n, p, z, ans, div[ArraySize];

void desc_fact_primi() {

	if (n % 2 == 0) {
		while (n % 2 == 0)
			n /= 2;
		div[++div[0]] = 2;
	}

	for (long long i = 3; i * i <= n; i += 2)
		if (n % i == 0) {
			while (n % i == 0)
				n /= i;
			div[++div[0]] = i;
		}

	if (n > 1)
		div[++div[0]] = n;
}

long long check(long long val) {

	long long i, j, sum, prod, cnt;

	sum = 0;
	for (i = 1; i < (1 << div[0]); i++) {
		prod = 1;
		cnt = 0;
		for (j = 0; j < div[0]; j++)
			if (i & (1 << j)) {
				cnt++;
				prod *= div[j + 1];
			}

		if (cnt % 2)
			sum += val / prod;
		else
			sum -= val / prod;
	}

	return val - sum;
}

long long caut_bin(long long st, long long dr) {

	long long mij, rez, aux;

	while (st <= dr) {
		mij = st + (dr - st) / 2;
		aux = check(mij);
		if (aux >= p) {
			rez = mij;
			dr = mij - 1;
		}
		else
			st = mij + 1;
	}

	return rez;
}

int main() {

	f >> n >> p;

	desc_fact_primi();

	ans = caut_bin(1, inf);

	g << ans << endl;

	f.close();
	g.close();

	return 0;
}