#include<stdio.h>

#define IN "frac.in","r",stdin
#define OUT "frac.out","w",stdout
#define ll long long

ll N , P ;
int E = 0; ll divz[32]; int st[32];
ll sum = 0 ;
void back(int k, int nrpuse, ll m)
{
	if(k == E+1)
	{
		if (nrpuse == 0)
			return ;
		ll prod = 1;
		for(int i = 1; i <= E ; ++i) 
			if(st[i] == 1)	prod *= divz[i];
		if(nrpuse % 2 == 0)
			sum -= m / prod;
		else sum += m / prod;
		return ;
	}
	st[k] = 0; back(k+1, nrpuse, m);
	st[k] = 1; back(k+1, nrpuse + 1, m);
}
ll cec(ll m)
{
	sum = 0;
	back(1, 0, m);
	return  m - sum;
}
int main()
{
	freopen(IN);
	freopen(OUT);
	scanf("%lld %lld",&N,&P);
	ll N1 = N;
	for(ll i = 2 ; i * i <= N ; ++i)
	{
		if(N1 % i == 0)	divz[++E] = i;
		while(N1 % i == 0) 	N1 /= i;
	}
	if(N1 != 1)	divz[++E] = N1;

	ll st = 1 , dr = ((ll)1<<62) , m, sol;
	while(st <= dr)
	{
		 m = (st + dr) / 2;
		 if(cec(m) >= P) 
		 { sol = m, dr = m - 1; }
		 else st = m + 1;
	}
	printf("%lld\n",sol);
	return 0;
}