#include <stdio.h>
long long n,p,sum,prod=1,nr=0;
int prim[20000],v[128];
void start(int poz,long long x){
if(prod>x)
return;
if(poz>v[0]){
if(nr>0){
if(nr%2) sum-=x/prod;
else sum+=x/prod;
}
}
else {
start(poz+1,x);
prod=(long long)prod*v[poz];
nr++;
start(poz+1,x);
nr--;
prod=(long long)prod/v[poz];
}
}
long long solve(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!=0)
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;
}