#include <fstream>
#include <vector>

using namespace std;

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

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

// se returneaza al m-lea numar care este prim cu n
long long int search_div(long long int m) {
	long long int rez = 0;
	for (long long int i = 0; i < 1 << div_vect.size(); i++) {
		long long int sign = 1, fact = 1;
		for (long long int j = 0; j < div_vect.size(); j++)
			if ((i >> j) & 1) {
				fact *= div_vect[j];
				sign *= -1;
			}
		rez += m / fact*sign;
	}
	return rez;
}

int main()
{
	f >> n >> p;
	// descompunere in factori primi
	for (long long int d = 2; d*d <= n; d++) {
		if (n % d == 0) {
			div_vect.push_back(d);
			while (n % d == 0) n /= d;
		}
	}
	if (n != 1) div_vect.push_back(n);
	// se cauta binar numarul prim cu n de pe pozitia p
	long long int lt = 0, rt = (long long int) 1<<61;
	while (rt - lt > 1) {
		long long int mid = lt + (rt - lt) / 2;
		if (search_div(mid) >= p) rt = mid;
		else lt = mid;
	}
	g << rt;
    return 0;
}