#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

long long n, p;
vector <int> fact;

//Care e numarul maxim de factori primi pe care il poate avea n?
//Answer =
//2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 -> 11 factori
long long functie(long long k) {
  long long s = 0;
  for(int i = 1; i < (1<<fact.size()); i++) {
    int nrbiti = 0;
    long long pret = 1;
    long long submult = i;
    for(int j = (int) fact.size() - 1; j >= 0; j--) {
      if((submult & 1) == 1) {
        pret = pret * 1LL * fact[j];
        nrbiti ++;
      }
      submult = (submult >> 1);
    }
    //cout<<i<<" -> "<<pret<<endl;
    if(nrbiti % 2 == 1)
      s -= (k/pret);
    else
      s += (k/pret);
   }
   return k+s;
}

long long binarysearch(long long from, long long to) { //from < sol <= to
  if(from < to) {
    long long mid = ((from + to) >> 1);
    if(functie(mid) < p)
      return binarysearch(mid + 1, to);
    else
      return binarysearch(from, mid);
  } else
    return from;
}

void decompose(long long n)
{
 long long d = 2;
  while(d*d <= n)
  {
    if(n % d == 0){
      fact.push_back(d);
    }
    while(n % d == 0)
      n /= d;
    d ++;
  }
  if(n > 1)
    fact.push_back(n);
}

int main() {
  in >> n >> p;
  decompose(n);
  //cout<<fact.size()<<" "<<fact[0]<<" "<<fact[1]<<endl;
  out << binarysearch(1LL, 1LL << 62);
  //cout << functie(5);
  return 0;
}