#include <bits/stdc++.h>
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
long long n, p, d, nrp, st, dr, mij, v, rez, i, j, nrc, pr, prime[100];
long long f(long long a)
{
    rez = a;
    for (i=1;i<(1LL<<nrp);i++){
        nrc = 0;
        pr = 1;
        for (j=0;j<nrp;j++){
            if (i & (1LL<<j)){
                nrc ++;
                pr = pr * prime[j+1];
            }
        }
        if (nrc % 2 == 1)
            rez = rez - a/pr;
        else
            rez = rez + a/pr;
    }
    return rez;
}
int main() {
    fin >> n >> p;
    for (d=2;d*d<=n;d++){
        if (n % d == 0){
            prime[++nrp] = d;
            while(n % d == 0)
                n /= d;
        }
    }
    if (n > 1)
        prime[++nrp] = n;

    st = 1;
    dr = (1LL << 61);
    while(st <= dr){
        mij = st + (dr - st)/2;
        v = f(mij);
        if (v >= p)
            dr = mij - 1;
        else
            st = mij + 1;
    }
    fout << st << '\n';
    return 0;
}