#include<stdio.h>
#include<math.h>
long long a[20];
int ver(long long med,int u,long long p)
{
	int lim,i,j,t,k;
	long long x,aux=med;
	lim=1<<u;
	for(i=1;i<lim;i++)
	{
		t=0;
		x=1;
		for(j=1,k=u;k>0;j=j<<1,k--)
			if(i&j)
			{
				x*=a[k];
				t++;
			}
		if(t%2==1)
			med-=aux/x;
		else
			med+=aux/x;
	}
	if(med>=p)
		return 1;
	return -1;
}
long long bs(long long p,int u)
{
	long long st,dr,last=1,med;
	int x;
	st=1;
	dr=2e18;
	while(st<=dr)
	{
		med=st+((dr-st)>>1);
		x=ver(med,u,p);
		if(x==1)
		{
			dr=med-1;
			last=med;
		}
		if(x==-1)
			st=med+1;
	}
	return last;
}
int main()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	long long n,p,i,z,x;
	int u=0;
	scanf("%lld%lld",&n,&p);
	if(n%2==0)
		a[++u]=2;
	while(n%2==0)
		n/=2;
	z=sqrt(n);
	for(i=3;i<=z && i<=n;i+=2)
		if(n%i==0)
		{
			a[++u]=i;
			while(n%i==0)
				n/=i;
		}
	if(n>1)
		a[++u]=n;
	x=bs(p,u);
	printf("%lld",x);
	return 0;
}