#include <cstdio>
#define Long long long
Long N,P,sol,d[15],nrd;
Long alfa(Long x){
     //alfa(x)=numarul de numere <=x care sunt prime cu N
     int i,j,nr;
     Long prod,r=0;
     for (i=1;i<(1<<nrd);++i){
         for (j=nr=0,prod=1;j<nrd;++j) 
           if ((1<<j)&i) prod*=d[j+1],nr++;
         if (nr&1) r+=(Long)(x/prod);
              else r-=(Long)(x/prod);
              }
     return x-r;
     }
int main(){
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    scanf("%lld %lld",&N,&P);
    Long ls=1,ld=1,mij,k;
    //factorizam N
    if (N%2==0) {d[++nrd]=2;
                 while (N%2==0) N/=2;}
    for (k=3;k*k<=N;k+=2)
      if (N%k==0){
        d[++nrd]=k;
        while (N%k==0) N/=k;}
    if (N!=1) d[++nrd]=N;
    //cautam binar rezultatul
    for (k=1;k<63;k++) ld*=2;
    while (ls<=ld){
          mij=(ls+ld)/2;
          k=alfa(mij);
          if (k>=P) sol=mij,ld=mij-1;
            else ls=mij+1;
          }
    printf("%lld",sol);
    return 0;
}