#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using pd = pair<double, double>;
using pld = pair<ld, ld>;
// #define LOCAL
#ifdef LOCAL
ifstream cin("input.txt");
ofstream cout("output2.txt");
#else
ifstream cin("frac.in");
ofstream cout("frac.out");
#endif
#define cin ::cin
#define cout ::cout


int main()
{
    ll N, P;
    cin >> N >> P;

    vector<int> distinct_pfs;
    int w{};
    ll aux = N;
    for (ll i = 2; i * i <= aux; ++i)
    {
        if (aux % i == 0)
        {
            distinct_pfs.emplace_back(i);
            ++w;
            for (; aux % i == 0; aux /= i)
                ;
        }
    }
    if (aux ^ 1)
    {
        distinct_pfs.emplace_back(aux);
        ++w;
    }

    // Returns the nr. of nrs. *NOT* coprime with 'N' which are <= 'ub'.
    auto pinex = [&](auto &self, const int idx, const ll ub) -> ll
    {
        static bool add{};
        static ll cur_prod{1};
        if (idx == w)
        {
            if (cur_prod == 1)
            {
                return 0ll;
            }
            if (add)
            {
                return ub / cur_prod;
            }
            return -ub / cur_prod;
        }

        ll ans{};
        // Take.
        cur_prod *= distinct_pfs[idx];
        add ^= 1;
        ans += self(self, idx + 1, ub);
        cur_prod /= distinct_pfs[idx];
        add ^= 1;

        // Don't take.
        ans += self(self, idx + 1, ub);

        return ans;
    };

    ll left = 1, right = 1ll << 61, ans;
    while (left <= right)
    {
        const ll cur_num = (left + right) / 2;
        const ll cur_res = cur_num - pinex(pinex, 0, cur_num);
        if (cur_res < P)
        {
            left = cur_num + 1;
        }
        else
        {
            ans = cur_num;
            right = cur_num - 1;
        }
    }
    cout << ans;
}