#include<fstream>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;

bool p[1000005];
int f[200],prim[100005],PR;


ll check(ll N, ll P){
     int k,F=0,i,j;
     ll sol=P, prod, nr;
     k=0;
     while(N>1)
     {
       ++k;
       if(N % k == 0)
       {
         f[++F]=prim[k];
         while(N%prim[k]==0) N/=prim[k];     
       }
       
       if(prim[k] > sqrt(N) && N>1)
       {
         f[++F]=N;
         N=0;           
       }
     }

     for(i=1;i<(1<<F);++i)
     {
       nr = 0; prod = 1;
       for(j=0;j<F;++j)
         if(i & (1<<j))
         {
           ++nr;
           prod = 1LL * prod * f[j+1];     
         }
       
       if(nr&1) nr = -1; else nr = 1;
       
       sol = sol + 1LL * nr * P / prod;
       
     }
  return sol;
}


int main(){
    ifstream cin("frac.in");
    ofstream cout("frac.out");
    ll N,P; int i,j;
    ll l,mid,r,sol;
    
    cin>>N>>P;
    
    for(i=2;i<=1000000;++i)
      if(!p[i])
      {
       for(j=2;j<=(1000000/i);++j)
         p[i*j]=1;
       prim[++PR]=i;   
      }
      
    l = 1; r =(1LL<<62);
    
    while(r-l>1)
    {
      mid = l + (r-l)/2LL;       
      if(check(N,mid) >= P) r=mid;
      else l=mid;                         
    }
    if(check(N,l)==P) sol=l;
    else sol=r;
               
    cout<<sol<<'\n';
    
 return 0;   
}