#include <fstream>
#include <vector>
using namespace std;
vector <long long> d;

long long nr(long long med)
{
    int dim = (1 << d.size());
    long long ans = 0;
    for (int i = 1; i < dim; i++)
    {
        long long prod = 1;
        int cnt = 0;
        for (int j = 0; (1LL << j) <= i; j++)
            if (i & (1LL << j))
        {
            cnt++;
            prod *= d[j];
        }
        if (cnt % 2 == 0)
            ans -= med / prod;
        else
            ans += med / prod;
    }
    return med - ans;
}
int main()
{
    ifstream cin("frac.in");
    ofstream cout("frac.out");
    long long n;
    int p;
    cin >> n >> p;
    long long dv = 2;
    while (dv * dv <= n)
    {
        if (n % dv == 0)
        {
            d.push_back(dv);
            while (n % dv == 0)
                n /= dv;
        }
        dv++;
    }
    if (n > 1)
        d.push_back(n);
    long long st = 1, dr = (1LL << 61) - 1, med, sol = -1;
    while (st <= dr)
    {
        med = ((st + dr) >> 1);
        if (nr(med) >= p)
        {
            sol = med;
            dr = med - 1;
        }
        else
            st = med + 1;
    }
    cout << sol;
}