#include <fstream>
#include <vector>

using namespace std;

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

vector < long long > fprimi;

long long p, ans(0);

long long lol(1), val(0);

bool par(1);

void muci_cu_blat_la_tava(int pc) {
    if (val < lol) {
        return;
    }
    if (par) {
        ans += val / lol;
    }
    else {
        ans -= val / lol;
    }
    par ^= 1;
    for (int i = pc - 1; i >= 0; --i) {
        lol *= fprimi[i];
        muci_cu_blat_la_tava(i);
        lol /= fprimi[i];
    }
}

long long cb() {
    long long pas = 1LL<<61, r(0);
    while (pas > 0) {
        ans = 0;
        val = r + pas;
        par = 1;
        lol = 1;
        muci_cu_blat_la_tava(fprimi.size());
        if (ans < p) {
            r += pas;
        }
        pas >>= 1;
    }
    return r + 1;
}

int main()
{
    long long n;
    cin >> n >> p;
    int a(2);
    while (a * a <= n) {
        if (n % a == 0) {
            fprimi.push_back(a);
            while (n % a == 0) {
                n /= a;
            }
        }
    }
    if (n > 1) {
        fprimi.push_back(n);
    }
    cout << cb();
    return 0;
}