#include <bits/stdc++.h>

using namespace std;

const long long MAX_A = 4611686018427387904;

long long n, p;

vector < long long > primes;

long long pin(long long val) {
  long long ans = 0;
  for (int perm = 1; perm < (1 << int(primes.size())); ++perm) {
    long long thisPerm = 1;
    int sign = 0;
    for (int j = 0; j < int(primes.size()); ++j) {
      if (((1 << j) & perm) > 0) {
        thisPerm = 1LL * thisPerm * 1LL * primes[j];
        sign ^= 1;
      }
    }
    if (sign > 0 && thisPerm != 0) {
      ans = 1LL * ans + (1LL * val / thisPerm);
    } else {
      ans = 1LL * ans - (1LL * val / thisPerm);
    }
  }
  return val - ans;
}

int main() {
  freopen("frac.in", "r", stdin);
  freopen("frac.out", "w", stdout);
  scanf("%lld %lld", &n, &p);
  long long lo = 0, ri = MAX_A, ans = 0;
  long long val = n;
  long long d = 2;
  while (d * d <= val) {
    if (val % d == 0) {
      primes.push_back(d);
      while (val % d == 0) {
        val /= d;
      }
    }
    if (d == 2) {
      ++d;
    } else {
      d += 2;
    }
  }
  if (val > 1) {
    primes.push_back(val);
  }
  while (lo <= ri) {
    long long mid = 1LL * lo + (ri - lo) / 2;
    if (pin(mid) >= p) {
      ans = mid;
      ri = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  printf("%lld", ans);
  return 0;
}