#include<fstream>
#include<cmath>
#define maxn 1000000
using namespace std;
int fact[50],nrf;

inline void descompune(long long val){
      int i=1; nrf=0;
       while (i<=sqrt(val)){
         i+=2;
          if (val%i==0) {fact[++nrf]=i; while (val%i==0&&val>1) val/=i; }
         }
       if (val%2==0) {fact[++nrf]=2; while (val%2==0&&val>1) val/=2; }
        if (val>1)fact[++nrf]=val;
}

long long neprime(long long val){
     long long nrsub=(1<<nrf)-1,i=0,rez=0;
      while (i<nrsub){
            ++i; long long aux=i,solc=1; int unu=0,pos=1;
            for (int j=1; j<=nrf&&aux!=0; ++j){
                if (aux&1==1) {solc*=fact[pos]; ++unu;}
                 aux=aux>>1; ++pos;
                 }
             if (unu%2==0) rez-=val/solc; else rez+=val/solc;
      }
  return(rez);
}           

int main(void){
    ifstream fin("frac.in");
    ofstream fout("frac.out");
    long long n,mid,p,l,r; fin>>n>>p;
     l=1; r=(long long)1<<(long long)61; descompune(n);
     while (l<=r){
           mid=(l+r)/2;
           if (mid-neprime(mid)>=p) r=mid-1; else l=mid+1;
           }
    fout<<l;
  return(0);
}