#include <fstream>
using namespace std;

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

#define last_step 1LL << 4

long long n, p, div[1000], rez, a;

void doPinex(long long poz, long long adan, long long sum) {
    int i;
    if(adan != 0) {
        if(adan % 2 == 0)
            rez += (a / sum);
        else
            rez -= (a / sum);
    }
    for(i = poz; i <= div[0]; ++i)
        doPinex(i + 1, adan + 1, sum * div[i]);
}

long long cauta_binar() {
    long long st = 1, fn = last_step, m;
    while(st < fn) {
        m = (st + fn) / 2;
        a = m; rez = a;
        doPinex(1, 0, 1);
        if(rez < p)
            st = m + 1;
        else
            fn = m;
    }
    return st;
}

int main() {
    int i;
    fin >> n >> p;
    for(i = 2; i * i <= n; ++i) {
        if(n % i == 0) {
            div[++div[0]] = i;
            while(n % i == 0)
                n /= i;
        }
    }
    if(n != 1)
        div[++div[0]] = n;
    fout << cauta_binar() << "\n";
    fout.close();
    return 0;
}