#include <fstream>

using namespace std;

#define MAX_N 64

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

long long N, P, F[MAX_N];
int Nrf;

long long count(long long x)
{
	long long nr = x;

	for(long long i = 1; i < (1LL << Nrf); ++i)
	{
		int nrx = 0;
		long long p = 1;

		for(int j = 1; j <= Nrf; ++j)
			if(i & (1LL << (j-1)))
				++nrx,
				p *= F[j];

		if(nrx & 1) nr -= (x / p);
		else nr += (x / p);
	}

	return nr;
}

int main()
{
	fin >> N >> P;

	for(long long i = 2; i*i <= N; ++i)
		if(N % i == 0)
			for(F[++Nrf] = i; N % i == 0; N /= i);

	if(N != 1)
		F[++Nrf] = N;
			
	long long lg = 1LL << 62, i;
	
	for(i = lg; lg; lg >>= 1)
		if(i + lg > 0 && count(i-lg) >= P)
			i -= lg;

	fout << i <<"\n";
}