#include <fstream>

using namespace std;

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

long long val, n, k, st, dr, med;
int ind, v[105];

void bkt(int poz, long long prod, int semn, long long x)
{
    if(poz > ind)
    {
        if(prod == 1)
            return;
        val += (x / prod) * semn;
        return;
    }
    bkt(poz + 1, prod, semn, x);
    bkt(poz + 1, prod * v[poz], -semn, x);
}

int main()
{
    fin >> n >> k;
    for(int i = 2; i * i <= n; i++)
        if(n % i == 0)
        {
            v[++ind] = i;
            while(n % i == 0)
                n /= i;
        }
    if(n != 1)
        v[++ind] = n;
    st = 1, dr = 1e18;
    while(st < dr)
    {
        med = (st + dr)/2;
        val = 0;
        bkt(1, 1, -1, med);
        val = med - val;
        if(val < k)
            st = med + 1;
        else
            dr = med;
    }
    fout << st;
    return 0;
}