#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define ll long long
#define MAX_P 1000000
ll M, A, B, fact[30],p,u,Min,x;
int fprim[80000];
bool prim[MAX_P];
void prec() {
    fill(prim + 2, prim + MAX_P, 1);
    for (int i = 2; i < MAX_P; i++)
        if (prim[i]) {
            for (int j = 2 * i; j < MAX_P; j += i)
                prim[j] = false;
            fprim[++fprim[0]] = i;
        }
}
long long solve(long long t) {

    ll sol = A;
    for (int i = 1; i < (1 << t); i++) {
        ll nr = 0, prod = 1;
        for (int j = 0; j < t; j++)
            if ((1 << j) & i) {
                prod = 1LL * prod * fact[j + 1];
                nr++;
            }

        if (nr % 2) nr = -1;
        else nr = 1;

        sol = sol + 1LL * nr * A / prod;
    }
    return sol;
}
int main() {

    freopen("frac.in", "r", stdin);
    freopen("frac.out", "w", stdout);
    prec();
    scanf("%lld%lld", &B,&x);
    ll t = 0, d = 0;
    while (B > 1) {
        d++;
        if (B % fprim[d] == 0) {
            fact[++t] = fprim[d];
            while (B % fprim[d] == 0)
                B /= fprim[d];
        }

        if (fprim[d] > sqrt(B) && B > 1) {
            fact[++t] = B;
            B = 1;
        }
    }
    p=1;
    u=(1ll<<61);
    Min=1ll<<61;
    while(p<=u)
    {
        A=(p+u)/2;
        if(solve(t)>=x)
        {
            if(A<Min) Min=A;
            u=A-1;
        }
        else p=A+1;
    }
    printf("%lld\n",Min);
    return 0;
}