#include<stdio.h>
#define NR 1<<6
#define ll long long
ll n,p;
int r; ll divz[NR]; char stiva[NR];
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(stiva[i]==1)	
				prod *= divz[i];
		if(!(nrpuse&1))
			sum-=m/prod;
		else 
			sum+=m/prod;
		return ;
	}
	stiva[k]=0; back(k+1,nrpuse,m);
	stiva[k]=1; back(k+1,nrpuse+1,m);
}
ll val(ll x)
{
	sum=0;
	back(1,0,x);
	return  x-sum;
}
ll cbin()
{
	ll i,step=((ll)1<<62);
	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;
}