#include<stdio.h>
long long prim[20];
long long n,p;
long long cate;
void precalc()
{
	long long n1=n;
	for(long long i=2; i*i<=n1; i++)
	{
		prim[++prim[0]]=i;
		while(n1%i==0)
			n1/=i;
	}
	if(n1!=1)
		prim[++prim[0]]=n1;
	for(int i=prim[0]+1; i<20; i++)
		prim[i]=1;
	cate=1<<prim[0];
}
long long f(long long x)
{
	long long rez=x;
	long long aux,j,k,nrb;
	//for(int i=1; i<=prim[0]; i++)
	//	rez+=(long long)(x/(long long)prim[i]);
	for(long long i=1; i<cate; i++)
	{
		aux=1;
		nrb=0;
		j=i;
		for(k=1; j; k++,j>>=1)
		{
			if(j&1)
			{
				aux*=prim[k];
				nrb++;
			}
		}
		if(nrb&1)
			rez-=x/aux;
		else
			rez+=x/aux;
	}
	return rez;
}
void caut()
{
	long long st=1,dr=1LL<<61,m;
	while(st!=dr)
	{
		m=(st+dr)>>1;
		if(p<=f(m))
			dr=m;
		else
			st=m+1;
	}
	//while(f(st)==p)
	//	st--;
	printf("%lld\n",st);
	//printf("%lld\n",f(13));
}
int main()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	scanf("%lld%lld",&n,&p);
	precalc();
	caut();
	return 0;
}