#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;

    g<<caut_bin(p);

    return 0;
}