#include <bits/stdc++.h>
using namespace std;
 
ifstream fin("frac.in");
ofstream fout("frac.out");
 
using ll = long long;
 
vector<int> prim;
 
ll verif (ll n) {
  ll sol = 0;
  for(int i = 1; i < (1 << prim.size()); i++) {
    ll p = 1;
    int nr = 0;
    for(int j = 0; j < (int)prim.size(); j++) {
      if (i & (1 << j)) {
        p *= prim[j];
        nr++;
      }
    }
    if(nr % 2)
      sol += n / p;
    else
      sol -= n / p;
  }
  return n - sol;
}
 
ll binarysearch(int p) {
  ll st = 1, dr = (1LL << 61), rez = 0;
  while (st <= dr) {
    ll mij = (st + dr) / 2;
    if(verif(mij) < p)
      st = mij + 1;
    else {
      dr = mij - 1;
      rez = mij;
    }
  }
  return rez;
}
 
int main() {
	ll n, p;
  fin >> n >> p;
  
  int d = 2;
  while(d * d <= n && n > 1) {
		if(n % d == 0) {
			prim.push_back(d);
			while(n % d == 0)
				n /= d;
		}
		d++;
	}
  if (n > 1)
    prim.push_back(n);
    
  fout << binarysearch(p);
  
  return 0;
}