#include <bits/stdc++.h>
using namespace std;

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

#define ll long long

ll n, k;
vector<ll> primes, divPrim;
const ll primeMax = 1000001;
bitset<primeMax> vis;
void primeGen()
{
  primes.push_back(2);
  for (ll i = 4; i < primeMax; i += 2)
    vis[i] = true;

  for (ll i = 3; i < primeMax; i += 2)
    if (vis[i] == false)
    {
      primes.push_back(i);
      for (ll j = i * i; j < primeMax; j += i)
        vis[j] = true;
    }

  for (ll div : primes)
    if (div > n)
    {
      break;
    }
    else if (n % div == 0)
    {
      divPrim.push_back(div);
      while (n % div == 0)
        n /= div;
    }

  if (n > 1)
    divPrim.push_back(n);
}

ll res(ll lim)
{
  ll size = divPrim.size(), steps = 1 << size, res = 0;

  for (ll i = 1; i < steps; i++)
  {
    ll temp = 1, cnt = 0;
    for (ll p = 0; p < size; p++)
      if (i & (1 << p))
        temp *= divPrim[p], cnt++;

    if (cnt % 2 == 0)
      res -= lim / temp;
    else
      res += lim / temp;
  }

  return lim - res;
}

int main()
{
  fin >> n >> k;
  primeGen();

  ll left = 1, right = 12e+9;
  while (left < right)
  {
    ll mid = (left + right) / 2;
    ll r = res(mid);

    if (r == k)
    {
      fout << mid - 1;
      return 0;
    }
    else if (r > k)
      right = mid;
    else
      left = mid;
  }

  return 0;
}