#include <stdio.h>
#define ll long long


ll i,j,N,P,nrf,Sol;
int fact[100];

void factori()
{
	i=1;
	while(N>1)
	{
		i++;
		if(N%i==0)
		{
			fact[++nrf]=i;
			while(N%i==0)
				N/=i;
		}
	}
}

ll verific(ll k)
{
	ll prod, nr, ns=((ll)1<<nrf)-1, R=0;
	for(i=1;i<=ns;i++)
	{
		prod=1; nr=0;
		for(j=0;j<nrf;j++)
			if(i&(1<<j))
			{
				prod*=fact[nrf-j];
				nr++;
			}
		if(nr&1)
			R+=k/prod;
		else
			R-=k/prod;
	}
	return k-R;
}

void cb()
{
	ll st=1, dr=(ll)1<<61,m;
	
	while(st<=dr)
	{
		m=st+(dr-st)/2;
		if(verific(m) >= P)
		{
			dr=m-1;
			Sol=m;
		}
		else
			st=m+1;
	}
}

int main()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	scanf("%lld %lld",&N,&P);
	factori();
	cb();
	printf("%lld",Sol);
}