#include <fstream>

using namespace std;
ifstream in ("frac.in");
ofstream out("frac.out");
long long v[100], n, nr, mask, p, d, i, total, sol, cate, st, dr, mid, x, j;

long long acata ( long long a ){
    total=0;
    for ( mask=1; mask < (1<<(nr+1)); mask++ ){
        cate = 0; sol =1;
        for ( j=0; j < nr; j++ )
            if ( (mask >> j) & 1 )
                sol *= v[j+1], cate++;
        if ( cate%2 ) total += a/sol;
        else total -= a/sol;
    }
    return (a-total)/2;
}

int main()
{
    in>>n>>p;
    d=2;
    while ( n > 1 ){
        if ( n%d == 0 )
            v[++nr] = d;
        while ( n%d == 0 ) n/=d;
        d++;
        if ( d*d > n && n > 1 ) d=n;
    }

    st=1; dr=(1LL<<61);
    while ( st <= dr ){
        mid = st + (dr-st)/2;
        x = acata ( mid );
        if ( x >= p ) dr = mid-1;
        else st = mid+1;
    }
    out << st;
    return 0;
}