#include <cstdio>
using namespace std;
const int NMAX = 1005;
long long int n, p, aux, nrnr, nrdiv, sol, prod, nr, rez, i, j, mij, st, dr;
long long int fact[NMAX];

int main()
{
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    scanf("%lld%lld", &n, &p);
    aux = n;
    for(i = 2;i <= n; ++i) {
        if(n % i == 0) {
            fact[++nrdiv] = i;
            while(!(n % i)) {
                n /= i;
            }
        }
    }
    st = 1;
    dr = (long long)1 << 61;
    nrnr = 1 << nrdiv;
    while(st <= dr) {
        mij = (st + dr) / 2;
        sol = 0;
        for(i = 1;i < nrnr; ++i) {
            nr = 0;
            prod = 1;
            for(j = 0;j < nrdiv; ++j) {
                if(((1 << j) & i) != 0) {
                    ++nr;
                    prod *= fact[j + 1];
                }
            }
            if(nr % 2) {
                nr = 1;
            }
            else {
                nr = -1;
            }
            sol += 1LL * nr * (mij / prod);
        }
        if(mij - sol < p) {
            st = mij + 1;
        }
        else {
            dr = mij - 1;
            rez = mij;
        }
    }
    printf("%lld\n", rez);
    return 0;
}