#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,100000000000000000ll);
	fout<<rasp;
	return 0;
}
void prec()
{
	int val=sqrt(n);
	int i=1;
	while(n>1 &&i<=val)
	{
		i++;
		if(n%i==0)
		{
			sol[++num]=i;
			while(n%i==0)
				n/=i;
		}
	}
	if(n>val)
	  sol[++num]=n;
}
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);
	  }
  }