#include <stdio.h>
long long n, p, sum, prod = 1, nr = 0;
int prim[20000], v[128];
void go(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 {
go(pos+1,x);
prod=(long long)prod*v[pos];
nr--;
go(pos+1,x);
nr--;
prod=(long long)prod/v[pos];
}
}
long long solve(long long x){
sum=x;
go(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 (solve((long long)crt + step) < p)

crt = (long long)crt + step;

printf("%lld\n", (long long)crt + 1);

return 0;

}