#include <fstream>
#include <iostream>
#define ll long long
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
ll p,n,v[1000001],k;


ll submult (ll a)
{
    ll rez=a, p, nrc, i,j;
    for(i=1; i < (1LL << k); i++)
    {
            nrc = 0;
            p = 1;
            for(j = 0;j < k; j++)
              if(i & (1LL << j))
                {
                    nrc++;
                    p*=v[j + 1];
                }

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

ll cautare(ll p)
{
  ll st, dr, mij;
  st = 1;
  dr = 1LL << 61;

  while(st <= dr)
  {
       mij = (st + dr) / 2;

       if (submult(mij) < p) st = mij + 1;
       else dr = mij - 1;
  }
  return st;
}

int main()
{
    ll i, j;
    f >> n >> p;
    i = 2;
    while (n > 1 && i * i <= n)
    {
        if(n % i == 0)
        {
            v[++k]=i;
            while(n%i==0) n=n/i;
        }
        i++;
    }
    if(n>1) v[++k]=n;

    g<<cautare(p);
    return 0;
}