#include <stdio.h>
long long n, p, sum, prod = 1, nr = 0;
int prim[20000], v[128];
void start(int pos,long long x){
if(prod>x)
return;
if(pos>v[0]){
if(nr>0){
if(nr%2) sum-=x/prod;
else sum+=x/prod;
}
} 
else {
start(pos+1,x);
prod=(long long)prod*v[pos];
nr--;
start(pos+1,x);
nr--;
prod=(long long)prod/v[pos];
}
}
long long rezolva(long long x){
sum=x;
start(1,x);
return sum;
}
int main(){
freopen("frac.in","r",stdin);
freopen("frac.out","w",stdout);
scanf("%lld %lld", &n, &p);
for (int i=2;i<=150000;i++) {
int ok=1;
for (int j=1;j<=prim[0]&&prim[j]*prim[j]<=i&&ok;j++)
if(i%prim[j]==0)
ok=0;
if(ok)
prim[prim[0]++] = i;
}
long long tmp = n;
for (int i = 1;(long long)prim[i]*prim[i]<=n;i++)
if(tmp%prim[i]==0){
v[v[0]++] = prim[i];
while(tmp%prim[i]==0)
tmp = (long long)tmp/prim[i];
}
if(tmp>1)
v[v[0]++]=tmp;
long long step=((long long)1)<<61,crt;
for(crt=0;step;step=(long long)step/2)
if(rezolva((long long)crt+step)<p)
crt=(long long)crt+step;
printf("%lld\n",(long long)crt+1);
return 0;
}