#include <fstream>

using namespace std;

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

long long n,p,m,i,j,v[30],k,st,dr,mid,w[30],s,prod,nr;

int main()
{
    fin >> n >> p;
    m = n;
    for (i=2; i*i<=m; i++)
        if (m%i == 0)
        {
            v[++k] = i;
            while (m%i == 0)
                m /= i;
        }
    if (m > 1)
        v[++k] = m;
    st = 1;
    dr = 1000000000000000000;
    while (st <= dr)
    {
        mid = (st+dr)/2;
        for (i=0; i<=k; i++)
            w[i] = 0;
        s = 0;
        while (w[0] == 0)
        {
            i = k;
            while (w[i] == 1 && i >= 1)
            {
                w[i] = 0;
                i--;
            }
            w[i] = 1;
            prod = 1;
            nr = 0;
            if (w[0] == 1)
                break;
            for (j=1; j<=k; j++)
                if (w[j] == 1)
                {
                    prod *= v[j];
                    nr++;
                }
            if (nr%2 == 0)
                s -= mid/prod;
            else
                s += mid/prod;
        }
        if (mid-s < p)
            st = mid+1;
        else
            dr = mid-1;
    }
    fout << st;
    return 0;
}