#include<fstream>
using namespace std;
long long n,p,nrp,prim[1<<4],prod[1<<10];
void pinex()
{long long i,j,x,p;
for(i=0;i<(1<<nrp);++i)
  {p=1;
  x=i;
  for(j=0;x;++j,x>>=1)
    if(x&1)
     p*=-prim[j];
  prod[i]=p;}}
long long calc(long long x)
{int i;
long long s=0;
for(i=0;i<(1<<nrp);++i)
  s+=x/prod[i];
return s;}
int main()
{long long i,pas=(long long)1<<61;
ifstream q("frac.in");
ofstream w("frac.out");
q>>n>>p;
for(i=2;i*i<=n;++i)
  if(n%i==0)
   {while(n%i==0)
	   n/=i;
	prim[nrp++]=i;}
if(n!=1)
 prim[nrp++]=n;
pinex();
for(i=0;pas;pas>>=1)
  if(calc(i+pas)<p)
   i+=pas;
w<<++i<<"\n";
return 0;}