#include <fstream>

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

long long acata ( long long a ){
    for ( i=0; i <= nr; i++ ) w[i]=0;
    total=0;
    while ( !w[0] ){
        i=nr; cate = 0;
        while ( w[i] ) w[i--]=0;
        w[i]=1; sol=1;
        if (w[0]) break;
        for ( i=1; i <= nr; i++ )
            if ( w[i] )
                sol *= v[i], cate++;
        if ( cate%2 ) total += a/sol;
        else total -= a/sol;
    }
    return a-total;
}

int main()
{
    in>>n>>p;
    d=2; long long m = n;
    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=m;
    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;
}