#include <fstream>
#define NMAX 1000001
using namespace std;

ifstream f("frac.in");
ofstream g("frac.out");
long long p,n,v[NMAX],nrc,rez,prim[NMAX],nrp,k;
bool ciur[NMAX];

//returneaza cardinalul reuniunii multimilor formate din multiplii factorilor primi ai lui n
long long calcul (long long a)
{
    long long rez=a, p, nrc, i,j;

    for(i=1;i<(1LL<<k);i++)
        {
            nrc = 0; // numarul de elemente din submultimea curenta
            p = 1; // produsul elementelor din submultimea curenta
            for(j = 0;j < k; j++)
              if(i & (1LL << j))
                {
                    nrc++;
                    p = p * v[j + 1];
                }

            if(nrc % 2 == 1) rez = rez - a / p;
            else rez = rez + a / p;
        }

    return rez;
}

long long caut_bin(long long p)
{
  long long s, d, m;
  s = 1; d = 1LL << 61;

  while(s < d)
  {
       m = (s + d) / 2;

       if (calcul(m) < p) s = m + 1;
       else d = m - 1;
  }
  return d;
}

int main()
{
    long long i, j;
    // ciurul lui Eratostene
   /* for(i = 2;i <= NMAX; i++)
      if(ciur[i] == 0)
        {
           prim[++nrp] = i;
           for(j = i + i; j < NMAX; j += i)
                ciur[j] = 1;
        }


        f >> n >> p;

    // construirea vectorului v cu factorii primi ai lui n
    i = 1;
    while (n > 1 && prim[i] * prim[i] <= n)
        {
            if(n % prim[i] == 0)
            {
                v[++k] = prim[i];
                while(n % prim[i] == 0) n /= prim[i];
            }
            i++;
        }
    if(n > 1) v[++k] = n;
    */

    f >> n >> p;

    i = 2;
    while (n > 1 && i * i <= n)
        {
            if(n % i == 0)
            {
                v[++k] = i;
                while(n % i == 0) n /= i;
            }
            i++;
        }


    g << caut_bin(p);

    return 0;
}