using namespace std;
#ifdef EZ
   #include "./ez/ez.h"
   const string FILE_NAME = "test";
#else
   #include <bits/stdc++.h>
   const string FILE_NAME = "frac";
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define cin fin
#define cout fout
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");

vector<ll> divi;

ll pinex(ll lim)
{
   ll ans = 0;
   for (ll x = 1; x < (1<<divi.size()); ++x)
   {
      ll prod = 1;
      for (int j = 0; j < divi.size(); ++j)
         if (x & 1<<j)
            prod *= divi[j];
      
      if (__builtin_popcount(x) % 2 == 1)
         ans += lim / prod;
      else
         ans -= lim / prod;
   }

   return lim - ans;
}


int main()
{
   ll n, p;
   cin >> n >> p;

   // descompunem in factori primi
   for (ll d = 2; d*d <= n; ++d)
      if (n%d == 0)
      {
         divi.pb(d);
         for (; n%d == 0; n /= d);
      }
   if (n != 1)
      divi.pb(n);
   
   // cautare binara
   ll st = n, dr = LLONG_MAX>>1, sol;
   while (st <= dr)
   {
      ll mj = st+dr >> 1;

      ll ans = pinex(mj);

      if (ans >= p)
         dr = mj-1,  sol = mj;
      else
         st = mj+1;
   }

   cout << sol;
}