#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
long long n,p,st[100],q,S,n1,ct;
long long divv[100];
bool viz[100];
long long N;
void Calcul()
     {long long i;
      q=1;
      for(i=1;i<=N;i++)
         q*=divv[st[i]];
         //if(n1==12)cout<<"("<<N<<") ";
      if(N%2==1)S-=n1/q;
       else S+=n1/q;
     }
void Back(int top)
     {long long i;
      if(top==N+1)Calcul();
      else
      for(i=st[top-1]+1;i<=ct;i++)
         {if(viz[i]==0)
            {st[top]=i;
             viz[i]=1;
             Back(top+1);
             viz[i]=0;
            }
         }
     }
int main()
{long long i,dr,st,ok;
 fin>>n>>p;
 n1=n;
 for(i=2;i<=n;i++)
    {if(n%i==0){ct++;divv[ct]=i;
                while(n%i==0)n/=i;
               }
    }

 //ct=divv[1].size();
 //for(i=1;i<=ct;i++)
    //fout<<divv[i]<<" ";
 st=1;
 dr=9223372036854775807;
 //cout<<dr;
 while(st!=dr)
 {n1=(st+dr)/2;
  S=n1;
  for(i=ct;i>=1;i--)
    {N=i;
     Back(1);
    }
    //cout<<n1<<" "<<S<<"\n";
  if(S>=p)dr=n1;
  else st=n1+1;
 }
 //fout<<S<<" ";
 while(ok==0)
 {ok=1;
  for(i=1;i<=ct;i++)
     if(st%i==0){st++;ok=0;break;}
 }
 fout<<st;
}