#include <bits/stdc++.h>
#define maxn 110000

using namespace std;
ifstream f("frac.in");
ofstream g("frac.out"); 
long long n, p;
bitset<maxn + 5> ciur;
vector<int> prime, factori;

uint64_t number(uint64_t bound)
{
  uint64_t rez = bound;
  for(uint64_t i = 1;i < (1 << factori.size());++i)
    {
      uint64_t nr = 0, prod = 1;
      for(uint64_t j = 0;j < factori.size();++j)
        if((1 << j) & i)
          prod *= 1LL * factori[j], ++nr;
      nr = (nr % 2 == 1) ? -1 : 1;
      rez += 1LL * nr * (bound / prod);
    }
  return rez;
}

uint64_t solve()
{
  uint64_t st = 1, dr = (1ULL << 61), mid, rez = (1ULL << 61), numbers;
  while(st <= dr)
  {
    mid = (st + dr) / 2;
    numbers = number(mid);
    if(numbers < p)
        st = mid + 1;
    else if(numbers >= p)
        dr = mid - 1;
    if(numbers == p)
      rez = min(mid, rez);
  }
  return rez;
}

void Read()
{
  f>>n>>p;
  for(int i = 2;i <= maxn;++i)
    if(!ciur.test(i))
      {
        prime.push_back(i);
        for(int j = i;j <= maxn;j += i)
          ciur.set(j);
      }
  int copn = n;
  for(auto it : prime)
  {
    if(n % it == 0)
      {
        factori.push_back(it);
        while(n % it == 0)
          n /= it;
      }
    if((it > sqrt(n) && n != 1) || n == 1)
      {
        factori.push_back(n);
        n = copn;
        break;
      }
  }
}

int main()
{
  Read();
  g<<solve();
  return 0;
}