#include <fstream>

using namespace std;

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

long long n, k, npow = 1, ans, val, poz, ind, v[100];

void bkt(int poz, long long p, int m, int x)
{
    if(poz > ind)
    {
        if(p == 1)
            return;
        if(m % 2 == 0)
            val -= x / p;
        else
            val += x / p;
        return;
    }
    bkt(poz + 1, p * v[poz], m + 1, x);
    bkt(poz + 1, p, m, 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;
    npow = 15000000000;
    for(int i = npow; i > 0; i >>= 1)
    {
            val = 0;
            bkt(1, 1, 0, ans + i);
            val = ans + i - val;
            if(val < k)
                ans = ans + i;
    }
    fout << ans + 1 << '\n';
    return 0;
}