#include <fstream>
#include <cmath>

#define maxrez 1LL*(1<<30)*(1<<30)*4+1
#define ll long long

using namespace std;

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

ll fac[32],lo,hi,prod,mid,n,P,s,f;

void decompose (ll n)
{
    for (int i=2; i*i <= n; ++i)
    {
        if (n%i == 0)
        {
            fac[++f] = i;

            while (n%i==0)
            {
                n /= i;
            }
        }
    }

    if (n!=1)
    {
        fac[++f] = n;
    }
}

void subsets (int k, int nr)
{
    for (int i=k; i<=f; ++i)
    {
        prod *= fac[i];
        subsets (i+1,nr+1);
        prod /= fac[i];
    }

    if (nr%2)
    {
        s += mid/prod;
    }
    else if (nr!=0)
    {
        s -= mid/prod;
    }
}

int main()
{
    fin>>n>>P;

    decompose (n);

    lo = -1, hi = maxrez;

    while (hi-lo > 1)
    {
        mid = (lo+hi)/2;

        prod = 1;
        s=0;
        subsets (1,0);

        if (mid <= s+P-1)
            lo = mid;
        else
            hi = mid;
    }

    fout<<hi;
}