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

ifstream fin ("frac.in");
ofstream fout ("frac.out");

typedef unsigned long long ull;

ull n, p;
vector <ull> v;

ull go(ull a) {
    ull fr = 0;
    for (int i = 1; i < (1 << n); ++i) {
        ull prod = 1, nr = 0;
        for (int j = 0; j < n; ++j)
            if (i & (1 << j)) {
                nr++;
                prod *= v[j];
            }
        if (nr % 2)
            fr += a / prod;
        else
            fr -= a / prod;

    }
    return a - fr;
}

int main() {
    fin >> n >> p;
    if (n % 2 == 0) {
        while (n % 2 == 0)
            n /= 2;
        v.push_back (2);
    }
    int aux = n;
    for (ull i = 3; i * i <= aux && n != 1; ++i)
        if (n % i == 0) {
            v.push_back (i);
            while (n % i == 0)
                n /= i;
        }
    if (n != 1)
        v.push_back (n);
    n = v.size();
    ull sol = 1LL << 61;
    for (ull step = 1LL << 60; step; step >>= 1)
        if (go (sol - step) >= p)
            sol -= step;
    fout << sol;
}