#include <fstream>
#include <cmath>
#include <vector>
using namespace std;
ifstream in("frac.in");
ofstream out("frac.out");
long long i, j, st, dr, mid, n, mask, k, o;
vector <long long> v;
long long v1[] = {-1, 1};
long long futere()
{
    long long ans = 0;
    for (long long mask = 1; mask < ((long long)1<<k); mask++)
    {
        long long p = 1, nr = 0;
        for (long long j = 0; j < k; j++)
        {
            if (mask & (((long long)1) << (j)))
            {
                nr++;
                p *= v[j];
            }
        }
        if (nr % 2 == 0)
            ans -= mid/p;
        else
            ans += mid/p;
    }
    ans = mid - ans;
    return ans;
}
void func()
{
    bool ok = 0;
    while (n % i == 0)
    {
        n/=i;
        ok=1;
    }
    if(ok==0)
        return;
    v.push_back(i);
}
int main()
{
    o = 61;
    dr = (((long long)1)<<o) + (long long)1;
    in >> n >> o;
    i=2;
    func();
    for (i = 3; i * i <= n; i += 2)
        func();
    if (n != 1)
        v.push_back(n);
    k=v.size();
    while (st+1 < dr)
    {
        mid = ((st+dr)>>((long long)1));
        if (futere() < o)
            st = mid;
        else
            dr = mid;
    }
    out << dr << '\n';
    return 0;
}