#include <cstdio>
#define MAXM 100000
long long div[MAXM];
inline long long cauta(long long x,int m){
    int p2=1<<m,i,nr,con,j;
    long long s=0,p;
    for(i=1;i<p2;i++){
         nr=i;
         p=1;
         con=0;
         for(j=0;j<m;j++){
              if(nr%2==1){
                  p*=div[j];
                  con++;
              }
              nr/=2;
         }
         if(con%2==1)
            s=s+(x/p);
         else
            s=s-(x/p);
    }
    return x-s;
}
int main(){
    FILE*fi,*fout;
    int m,e,i;
    long long rez,pas,d,n,p;
    fi=fopen("frac.in" ,"r");
    fout=fopen("frac.out" ,"w");
    fscanf(fi,"%lld%lld" ,&n,&p);
    d=2;
    m=0;
    while(d*d<=n){
         e=0;
         while(n%d==0){
               n/=d;
               e++;
         }
         if(e>0){
             div[m]=d;
             m++;
         }
         d++;
    }
    if(n>1)
       div[m++]=n;
    rez=0;
    pas=1;
    for(i=0;i<60;i++)
        pas=pas*2;
    while(pas>0){
          if(cauta(rez+pas,m)<p)
              rez+=pas;
          pas/=2;
    }
    fprintf(fout,"%lld" ,rez+1);
    fclose(fi);
    fclose(fout);
    return 0;
}