#include<fstream>
#include<cmath>
#define maxn 1000000
using namespace std;
int fact[50],nrf,prime[100001],nrp;
bool viz[1000001];

inline void ciur(){
          nrp=1; prime[nrp]=2;
         for (int i=3; i<=maxn; i+=2)
          if (viz[i]==false){
                       prime[++nrp]=i;
                        for (int j=2; j<=maxn/i; ++j) viz[i*j]=true;
                  }       
}
inline void descompune(long long val){
       int i; nrf=0;
        for (i=1; prime[i]<=sqrt(val)&&i<=nrp; ++i)
         if (val%prime[i]==0){ fact[++nrf]=prime[i]; while (val%prime[i]==0&&val>1) val/=prime[i]; }
       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; ciur();
     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);
}