#include<fstream>
#include<cmath>
using namespace std;
bool apare[5400000];
int prim[5400000],np;
int sol[540],num,a;
long long n,rasp,P;
void prec();
long long numarare(long long A);
void cautare(long long st,long long dr);
ofstream fout("frac.out");
int main()
{
	ifstream fin("frac.in");
	fin>>n>>P;
	rasp=1000000000000000000ll;
	prec();
	//int i;
	//for(i=1;i<=num;i++)
	  // fout<<sol[i];
	cautare(1,10000000000000ll);
	fout<<rasp;
	return 0;
}
void prec()
{
	prim[++np]=2;
	int val=sqrt(n),i,j;
	for(i=2;i*2<=val;i++)
	    apare[i*2]=1;
	for(i=3;i*i<=n;i+=2)
	   if(apare[i]==0)
	   {
		   prim[++np]=i;
		   for(j=2;i*j<=val;j++)
		       apare[i*j]=1;
		}
 
	int copie=n;
	for(i=1;i<=np;i++)
	{
		if(copie%prim[i]==0)
		{
			sol[++num]=prim[i];
			while(copie%prim[i]==0)
			     copie/=prim[i];
	     }
	 }
	 if(copie>1 && copie>val)
	   sol[++num]=copie;	     
}
long long numarare(long long A)
{
	long long nrf=(long long)(1<<num)-1,R=0;
	long long nr=0,i;
	for(i=1;i<=nrf;i++)
	{
		long long prod=1;
		nr=0;
		for(int j=0;j<num;j++)
		{
			if(i & (1<<j))
			  prod=(long long)prod*sol[j+1],nr++;
		 }
		// fout<<prod;
		 if(nr%2==1)
		   R+=(long long)A/prod;
		 else
		   R-=(long long)A/prod;
		 //fout<<" "<<A<<endl;  
	   }
	   return A-R;
}   
void cautare(long long st,long long dr)
{
	if(st==dr)
	{
		if(numarare(st)==P && st<rasp)
		  rasp=st;
		return ;
	}
	else
	{
		long long mij=(st+dr)/2;
		long long a=numarare(mij);
		if(a>=P)
		{
			if(a==P && mij<rasp)
			   rasp=mij;
			cautare(st,mij);
		}
		else
		   cautare(mij+1,dr);
	  }
  }