#include<stdio.h>
#define L long long
L n,p,nn,f[20],nf,d,left,right,m,middle,pp,i,s,pr,j;
void readd(),facto(),solve();
int main()
{
	readd();
	facto();
	solve();
	return 0;
}
void readd()
{
	freopen("frac.in","rt",stdin);
	freopen("frac.out","wt",stdout);
	scanf("%lld%lld",&n,&p);
}
void facto()
{       nn=n;
	if(nn%2==0){f[nf++]=2;while(nn%2==0)nn/=2;}
	d=3;
	while(d*d<=nn)
	{  if(nn%d==0){f[nf++]=d;while(nn%d==0)nn/=d;}
	   d+=2;
	}
	if(nn>1){f[nf++]=nn;}
}
void solve()
{
   left=0;right=1<<61;
   m=(1<<nf)-1;
   while(right-left-1)
   { middle=(right+left)/2;
     pp=middle;
     for(i=1;i<=m;i++)
     { s=1;pr=1;
       for(j=0;j<nf;j++)
	if(i&(1<<j)){pr*=f[j];s=-s;}

       pp+=s*(middle/pr);
     }
       if(pp<p)left=middle;
       else right=middle;
   }
   printf("%lld\n",right);

}