#include<cstdio>
using namespace std;
#define MAX_N 128
#define ll long long
ll N, P;
ll a[MAX_N], a_len;
ll nr_ordine(ll X)
{
	ll i,j, nr, p, n = X;
	for(i = 1; i < (1<<a_len); ++i)
	{
		for(p = 1, j = 0, nr = 0; j < a_len; ++j)
			if((1<<j) & i)
			{
				++nr;
				p*=a[j+1];
			}
		if(nr&1) X -= (n/p);
		else X += (n/p);
	}
	return X;
}
int main()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	scanf("%lld%lld",&N,&P);
	ll i,j,m, r,sol=0;
	if(!(N&1)) { for(;!(N&1); N>>=1); a[++a_len] = 2; }
	for(i=3; i*i <= N; i+=2)
		if(N%i==0)
		{
			a[++a_len] = i;
			for(;N%i==0;N/=i);
		}
	if(N>1) a[++a_len] = N;
	i = 1; j = (1LL<<60)-1;  
	while(i<=j)
	{
		m = (i+j)/2;
		r = nr_ordine(m);
		if(r == P) sol = m;
		if(r < P) i = m+1;
		else j = m-1;
	}
	printf("%lld\n",sol);
	return 0;
}