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

ifstream in { "frac.in" };
ofstream out { "frac.out" };

int64_t P;
vector<int64_t> d;
int64_t sol;

void init() {
    int64_t n;
    in >> n >> P;

    auto desc = [&n](int64_t x) {
        if (n % x == 0) {
            d.push_back(x);
            do
                n /= x;
            while (n % x == 0);
        }
    };

    desc(2);
    desc(3);

    for (int64_t i { 5 }; i * i <= n; i += 6) {
        desc(i);
        desc(i + 2);
    }

    if (n != 1)
        desc(n);
}

int64_t noFrac(int64_t maximum) {
    int64_t sol { 0 };
    for (int i { 1 }; i < 1 << d.size(); ++i) {
        int64_t prod { 1 }, noSets { 0 };
        for (int j { 0 }; j < d.size(); ++j)
            if (i & (1 << j)) {
                ++noSets;
                prod *= d[j];
            }

        sol += (noSets % 2 ? 1 : -1) * (maximum / prod);
    }

    return sol;
}

void solve() {
    for (int64_t stg { 1 }, drp { 1LL << 61 }; stg <= drp;) {
        int64_t mij { stg + (drp - stg) / 2 };
        int64_t noF { mij - noFrac(mij) };

        if (noF >= P) {
            sol = mij;
            drp = mij - 1;
        } else {
            stg = mij + 1;
        }
    }
}

int main() {
    init();
    solve();
    out << sol;
}