#include <fstream>

using namespace std;

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

long long n, p, factori[10009], cnt;

void descompunere(long long n) {
    if (n % 2 == 0) {
        factori[++cnt] = 2;
        while (n % 2 == 0)
            n /= 2;
    }

    for(long long i = 3; i * i <= n; i += 2)
        if (n % i == 0) {
            factori[++cnt] = i;
            while (n % i == 0)
                n /= i;
        }

    if (n != 1)
        factori[++cnt] = n;

}


long long nr(long long a, long long b) {
    long long sol = a;
    for (int i = 1; i < (1 << cnt); i++) {
        long long nr = 0, prod = 1;
        for (int j = 0; j < p; j++)
            if ((1 << j) & i) {
                prod = 1LL * prod * factori[j + 1];
                nr++;
            }
        if (nr % 2) nr = -1;
        else nr = 1;
        sol = sol + 1LL * nr * a / prod;
    }
    return sol;
}

long long bs(long long p) {
    long long st = 1, dr = (1LL << 61);

    while (st <= dr) {
        long long mij = (st + dr) / 2;
        if (nr(mij, n) < p) 
            st = mij + 1;
        else
            dr = mij - 1;
    }

    return st;
}

int main() {

    in >> n >> p;

    descompunere(n);

    cout << bs(p);

    return 0;
}