#include <bits/stdc++.h>
#define ll long long

using namespace std;

ifstream fin ("frac.in");
ofstream fout ("frac.out");

vector<int>prim;
ll n, p;

long long verif (long long n) {
  long long sol = 0;
  for (int i = 1; i < (1 << prim.size()); i++) {
    ll p = 1;
    int nr = 0;
    for (int j = 0; j < prim.size(); j++) {
      if (i & (1 << j)) {
        p *= prim[j];
        nr++;
      }
    }
    if (nr % 2)
      sol += n / p;
    else
      sol -= n / p;
  }
  return n - sol;
}

long long bs () {
  ll st = 1, dr = (1LL << 61), rez;
  while (st <= dr) {
    long long mij = (st + dr) / 2;
    if (verif(mij) < p)
      st = mij + 1;
    else {
      dr = mij - 1;
      rez = mij;
    }
  }
  return rez;
}

int main()
{
  fin >> n >> p;
  if (n % 2 == 0) {prim.push_back(2); while (n % 2 == 0) n /= 2;}
  int d = 3;
  while (d * d <= n && n > 1) {
    if (n % d == 0){
      prim.push_back(d);
      while (n % d == 0)
        n /= d;
    }
    d += 2;
  }
  if (n > 1)
    prim.push_back(n);
  fout << bs();
  return 0;
}