#include <stdio.h> 
#include <math.h>
long long n,p;
int prim[20],nc;
void citire()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	scanf("%lld%lld",&n,&p);
}
void factprim(long long x)
{
	long long q=x,w,exp,d;
	long long t,sq=(long long)sqrt(x);
	for (d=2; d<=sq; d++)
	{
		if (q%d==0)
		{
			prim[++nc]=d;
			while (q%d==0)
				q/=d;
		}
	}
	if (q!=1)
		prim[nc++]=q;
}
void calcul(long long y,int &nrb,long long &prod)
{
	nrb=0;
	prod=1;
	for (int i=1; i<=nc; ++i,y>>=1)
		if (y&1)
		{
			prod=prod*prim[i];
			++nrb;
		}
}

long long f(long long x)
{
	long long s=x,i,prod;
	int nrbiti;
	for (i=1; i<(1<<nc); i++)
	{
		calcul(i,nrbiti,prod);
		if(nrbiti&1)
			s-=x/prod;
		else
			s+=x/prod;
	}
	return s;
}
long long solvez0r()
{
	long long m,st=1,dr=(long long)1<<(long long)61;
	while (st!=dr)
	{
		m=(st+dr)>>1;
		
		if (p<=f(m))
			dr=m;
		else
			st=m+1;
	}
	return st;
}
int main()
{
	citire();
	factprim(n);
	printf("%lld",solvez0r());
}