#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

typedef unsigned long long ull;

ull N, K;
ull V[16];
int nr;
ull sel[16];

void descompune()
{
	for (ull i(2); i*i <= N; ++i)
		if (N % i == 0) {
			V[++nr] = i;
			while (N % i == 0)
				N /= i;
		}
	if (N)
		V[++nr] = N;
}

ull ver(ull a)
{
	ull s(0);
	memset(sel, 0, sizeof(sel));

	while (sel[0] == 0) {
		for (ull i = nr; i >= 0; --i)
			if (sel[i] == 0) {
				sel[i] = 1;
				break;
			} else {
				sel[i] = 0;
			}
		ull p(1), t(0);
		for (ull i = nr; i >= 1; --i)
			if (sel[i]) {
				p *= V[i];
				t = !t;
			}
		if (p == 1)
			break;
		if (t == 0)
			s -= a/p;
		else
			s += a/p;
	}

	return a - s;
}

ull cauta(ull p, ull r)
{
	/*cout << p << " " << r << endl;*/
	if (p == r)
		return p;
	ull q = p + (r - p) / 2;
	
	if (ver(q) >= K)
		return cauta(p, q);
	return cauta(q+1, r);
}

int main(int argc, char *argv[]) 
{
	ifstream fin("frac.in");
	fin >> N >> K;
	fin.close();

	descompune();

	ull max = (ull)1 << 61;
	ofstream fout("frac.out");
	fout << cauta(0, max) << endl;
	fout.close();

	return 0;
}