#include<stdio.h>
#define N 1<<5
#define ll long long
ll n,p;
int r; ll divz[N]; char st[N];
ll sum;
void back(int k,int nrpuse,ll m)
{
	if(k==r+1)
	{
		if (nrpuse==0)
			return ;
		ll prod = 1;
		for(int i =1; i<=r ; i++) 
			if(st[i]==1)
				prod*=divz[i];
		if(nrpuse&1)
			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 val(ll x)
{
	sum = 0;
	back(1,0,x);
	return x-sum;
}
ll cbin()
{
	long long i,step=((ll)1<<61);
	for (i=0; step; step>>=1)
		if (val(i+step)<p)
			i+=step;
	return ++i;
}
int main()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	scanf("%lld%lld",&n,&p);
	for(ll i = 2; i*i<=n ; i++)
	{
		if(n%i==0)	
			divz[++r]=i;
		while(n%i== 0) 	
			n/=i;
	}
	if(n!=1)	
		divz[++r]=n;
	printf("%lld\n",cbin());
	return 0;
}