#include <bits/stdc++.h>
#define DIM 105

using namespace std;

ifstream f("frac.in");
ofstream g("frac.out");

long long divi[DIM], v[DIM], m, n, k;

bool pinex(long long p)
{
    long long ans = 0;
    for (int i = 0; i <= m; i++)
        v[i] = 0;

    while (!v[0])
    {
        long long i = m;
        while (v[i] == 1)
        {
            v[i] = 0;
            i--;
        }
        long long prod = 1, nr = 0;
        v[i] = 1;
        for (int i = 1; i <= m; i++)
            if (v[i] == 1)
                prod *= divi[i], nr++;
        if (prod != 1)
        {
            if (nr % 2 == 1)
                ans += p / prod;
            else
                ans -= p / prod;
        }
    }

    if (ans > 0)
        p -= ans;
    else
        p += ans;
    if (p < k)
        return 0;
    else
        return 1;
}

int main()
{
    f >> n >> k;

    for (long long d = 2; d * d <= n && n != 1; d++)
    {
        long long nr = 0;
        while (n % d == 0)
        {
            n /= d;
            nr++;
        }
        if (nr >= 1)
            divi[++m] = d;
    }

    if (n != 1)
        divi[++m] = n;

    long long st = 1, dr = (1LL << 61), ans = 1;
    while (st <= dr)
    {
        long long mid = (st + dr) / 2;
        if (pinex(mid))
            dr = mid - 1;
        else
            st = mid + 1;
    }

    g << st;
    return 0;
}