#include <cstdio>
using namespace std;
const long long MAX = (((1LL* 1) << 61) + 1);
long long a, v[20], l;
inline long long solve(int c)
{
    long long nr = -1;
    for (int i = 0; i <= l; ++i)
        if ((c & (1 << i)) != 0)
            nr = nr * -v[i];
    return a / nr;
}
inline long long pinex()
{
    int lim; long long ans;
    lim = (1 << (l + 1));
    ans = 0;
    for (int i = 1; i < lim; ++i)
        ans += solve(i);
    return a - ans;
}
int main()
{
    freopen("frac.in", "r", stdin);
    freopen("frac.out", "w", stdout);
    long long x, nr, st, dr, last, rez;
    scanf("%lld %lld", &x, &nr);
    l = -1;
    for (long long d = 2; d * d <= x; ++d)
        if (x % d == 0)
        {
            while (x % d == 0)
                x /= d;
            v[++l] = d;
        }
    if (x > 1)
        v[++l] = x;
    st = 1; dr = MAX;
    while (st <= dr)
    {
        a = (st + dr) / 2;
        rez = pinex();
        if (rez >= nr)
        {
            last = a;
            dr = a - 1;
        }
        else
            st = a + 1;
    }
    printf("%lld", last);
    return 0;
}