#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#define ll long long
#define mod 1000000007
#define pmax 1095400
using namespace std;
ifstream cin("frac.in");
ofstream cout("frac.out");
bool ciur[1095401];
vector<ll> prim, fact;
ll n, p;
int pop2(long long x) 
{
    int ans = 0;
    while (x)
    {
        if (x % 2 == 1)
            ans++;
        x /= 2;
    }
    return ans;
}
ll ok(ll nr)
{
    ll ans = nr, p;
    ll sz = fact.size();
    for (ll mask = 1; mask < (1LL << sz); mask++)
    {
        if (pop2(mask) % 2 == 1)
            p = -1;
        else p = +1;
        ll a = 1, aux = mask, k = 0;
        while (aux)
        {
            if (aux % 2 == 1)
                a *= fact[k];
            k++;
            aux /= 2;
        }
        ans += p * (nr/a);
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    for (int i = 2; i <= pmax; i++)
    {
        if (ciur[i]) continue;
        prim.push_back(i);
        for (int j = i * i; j <= pmax; j+=i)
            ciur[j] = 1;
    }
    cin >> n >> p;
    for (int i : prim)
    {
        if (n % i == 0)
        {
            fact.push_back(i);
            while (n % i == 0)
                n /= i;
        }
        if (i > n)
            break;
    }
    if (n > 1)
        fact.push_back(n);

    ll l = 1, r = (1LL << 61) + 1;
    while (l < r)
    {
        ll mid = (l + r) / 2;
        if (ok(mid) < p)
            l = mid + 1;
        else
            r = mid;
    }
    cout << l;
    return 0;
}