#include<stdio.h>

long long n,p,nrp,prim[20];

void desc(long long n)//deteremina divizorii primi ai lui n
{
	for(long long i=2;i*i<=n;++i)
		if(n%i==0)
		{
			prim[++nrp]=i;
			while(n%i==0)
				n/=i;
		}
	if(n!=1)
		prim[++nrp]=n;
}

void calcul(long long y,int &nrb,long long &prod)
//returneaza prin referinte nrb=nr de biti 1 din reprez lui y
//si prin prod=produsul factorilor primi din 
//descompunerea lui n corespunzatori bitilor 1
{
	nrb=0;
	prod=1;
	for(int i=1 ; i<=nrp ; ++i,y>>=1)
		if(y&1)
		{
			prod*=prim[i];
			++nrb;
		}
}

long long f(long long x)
//calculeza numarul de numere prime cu n, 
//mai mici sau egale cu x
{
	long long s=x,i,prod;
	int nrbiti;
	for(i=1 ; i < (1<<nrp) ; ++i)
	{
		calcul(i,nrbiti,prod);
		if(nrbiti&1)//<=>nrbiti%2==1
			s-=x/prod;
		else
			s+=x/prod;
	}
	return s;
}

long long rez()
{
	long long m,st=1,dr=(long long)1<<(long long)61;
	//caut binar solutia
	while(st!=dr)
	{
		m=(st+dr)>>1;
		if(p<=f(m))
			dr=m;
		else
			st=m+1;
	}
	return st;
}

int main()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	scanf("%lld%lld",&n,&p);
	desc(n);
	printf("%lld\n",rez());
	return 0;
}