#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
ifstream fin ("frac.in");
ofstream fout ("frac.out");
#define cin fin
#define cout fout
#endif

#define int int64_t

int n, p, c;
vector<int> d;

void gen_divp (int x)
{
    d.clear();
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            d.push_back (i);
            while (x % i == 0)
                x /= i;
        }
    }
    if (x > 1)
        d.push_back (x);
}

void dfs (int index, int dc, int poz, int urm)
{
    if (index > 0)
    {
        if (index % 2 == 0)
            c = c - urm / dc;
        else
            c = c + urm / dc;
    }
    for (int i = poz + 1; i < d.size(); i++)
    {
        dc = dc * d[i];
        dfs (index + 1, dc, i, urm);
        dc /= d[i];
    }
}

int32_t main()
{
    cin >> n >> p;
    gen_divp (n);
    int st = 1, dr = LLONG_MAX;
    while (st <= dr)
    {
        int mid = (st + dr) / 2;
        c = 0;
        dfs (0, 1, -1, mid);
        int nr = mid - c;
        if (nr < p)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    cout << st << '\n';
}