#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> listaDiv;

ll solve(ll n) {
  ll v[100];
  ll ans = 0;
  memset(v, 0LL, sizeof v);
  /// ma uit in v de la 0 la nrdiv
  bool ok = true;
  while(v[0] != 1 and ok) {
    ll i = static_cast<ll>(listaDiv.size());
    while(v[i] == 1 and i >= 0)
      v[i --] = 0;
    if(i) {
      ll putere, x = 0;
      putere = v[i] = 1;
      for(register ll i = 1; i <= static_cast<ll>(listaDiv.size()); ++ i) {
        if(v[i] == 1) {
          ++ x;
          putere *= listaDiv[i - 1];
        }
      }
      int semn = (x & 1) ? +1 : -1;
      ans += (n / putere) * semn;
    } else
      ok = false;
  }
  return ans = n - ans;
}

int main() {
  freopen("frac.in", "r", stdin);
  freopen("frac.out", "w", stdout);
  ll N, P;
  scanf("%lld%lld", &N, &P);
  ll d = 2LL;
  while(d * d <= N) {
    if(N % d == 0) {
      listaDiv.push_back(d);
      while(N % d == 0)
        N /= d;
    }
    ++ d;
  }
  if(N > 1)
    listaDiv.push_back(N);
  ll st, dr, med, ans;
  st = 0, dr = 1LL << 61;
  while(dr - st > 1) {
    med = st + ((dr - st) >> 1);
    ll cand = solve(med);
    if(cand == P)
      ans = med;
    if(cand >= P)
      dr = med - 1;
    else
      st = med + 1;
  }
  printf("%lld\n", ans);
  return 0;
}