#include <cstdio>
#define LOG 100
long long div[LOG+1];
int k;
inline long long check(long long val){
    long long ans=0;
    for(int conf=1;conf<(1<<k);conf++){
       long long prod=1;
       int cnt=0;
       for(int i=0;i<k;i++)
          if(conf&(1<<i)){
             cnt++;
             prod*=div[i];
          }
       if(cnt&1)
         ans+=val/prod;
       else
         ans-=val/prod;
    }
    return ans;
}
int main(){
   FILE*fi,*fout;
   long long n,p;
   fi=fopen("frac.in" ,"r");
   fout=fopen("frac.out" ,"w");
   fscanf(fi,"%lld %lld " ,&n,&p);
   int d=2;
   k=0;
   while(1LL*d*d<=n){
      int exp=0;
      while(n%d==0){
         n/=d;
         exp++;
      }
      if(exp>0)
        div[k++]=d;
      d++;
   }
   if(n>1)
     div[k++]=n;
   long long rez=0;
   for(long long pas=(1LL<<61);pas;pas>>=1)
     if(rez+pas-check(rez+pas)<p)
       rez+=pas;
   fprintf(fout,"%lld" ,rez+1);
   fclose(fi);
   fclose(fout);
   return 0;
}