#include <bits/stdc++.h>

using namespace std;

int main() {
  ifstream cin("frac.in");
  ofstream cout("frac.out");

  long long n, p; cin >> n >> p;
  vector<long long> fact;
  for (int i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      fact.emplace_back(i);
      while (n % i == 0) {
        n /= i;
      }
    }
  }
  if (n != 1) {
    fact.emplace_back(n);
  }
  function<long long(int, long long, int, long long)>
  Count = [&](int pos, long long mult, int sgn, long long m) {
    if (mult > m) return 0LL;
    if (pos == (int)fact.size()) {
      if (mult == 1LL) return 0LL;
      return sgn * m / mult;
    }
    long long ans = 0LL;
    ans += Count(pos + 1, mult, sgn, m);
    ans += Count(pos + 1, mult * fact[pos], -sgn, m);
    return ans;
  };
  long long ans = 0LL;
  for (long long step = 1LL << 61; step > 0; step >>= 1) {
    if (ans + step <= (1LL << 61) && ans + step - Count(0, 1, -1, ans + step) < p) {
      ans += step;
    }
  }
  cout << ans + 1 << endl;
}