#include <fstream.h>
#include<values.h>
long n, p, s, d, l, r, m, f, sol;
long i, nr, j, nrb;
long dp[20];
int main()
{ifstream q("frac.in");
ofstream w("frac.out");
cin>>n>>p;
nr=0;
d=1;
while(n>1&&d*d<=n)
   {d++;
   if(n%d==0)
    {nr++;
    dp[nr]=d;
    while(n%d==0)
       n=n/d;}}
if(n>1)
 {nr++;
 dp[nr]=n;}
l=0;
r=MAXLONG;
while(l+1<r)
   {m=(l+r)/2;
   s=m;
   for(i=1;i<(1<<nr);i++)
     {nrb=0;
     f=1;
     for(j=0;j<nr;j++)
       {if(i&(1<<j))
	 {nrb++;
	 f=f*dp[j+1];}}
     if(nrb%2==0)
      s=s+(m/f);
     else
      s=s-(m/f);}
     if(s==p)
      sol=m;
     if(s>=p)
      r=m;
     else
      l=m;}
cout<<sol;
return 0;
}