#include<fstream>
#include<bitset>

using namespace std;

ifstream fin( "frac.in" );
ofstream fout( "frac.out" );

typedef long long i64;

const int dim_ciur = 109544;
const int nr_prime = 10414;
const i64 inf = 2305843009213693952;
i64 ans;
int nrp, pr[ nr_prime ];
int nrd, p[ nr_prime + 1 ];
bitset <dim_ciur> ciur;

void precalc() {
    for( int i = 3; i * i < dim_ciur; ++ i ) {
        if ( ciur[ i ] == 0 ) {
            for( int j = i * i; j < dim_ciur; j += i ) {
                ciur[ j ] = 1;
            }
        }
    }
    nrp = 0;
    pr[ nrp ++ ] = 2;
    for( int i = 3; i < dim_ciur; i += 2 ) {
        if ( ciur[ i ] == 0 ) {
            pr[ nrp ++ ] = i;
        }
    }
}
void descomp( i64 x ) {
    nrd = 0;
    for( int i = 0; i < nrp; ++ i ) {
        if ( x % pr[ i ] == 0 ) {
            p[ nrd ++ ] = pr[ i ];
            while ( x % pr[ i ] == 0 ) {
                x /= pr[ i ];
            }
        }
    }
    if ( x > 1 ) {
        p[ nrd ++ ] = x;
    }
}
void pinex( i64 prod, int poz, i64 b ) {
    ans += b / prod;
    for( int i = poz; i < nrd; ++ i ) {
        pinex( -prod * p[ i ], i + 1, b );
    }
}
i64 ind( i64 x ) {
   ans = 0;
   pinex( 1, 0, x );
   return ans;
}
int main() {
    i64 a, k;
    fin >> a >> k;
    precalc();
    descomp( a );
    i64 sol = inf;
    for( i64 step = inf / 2; step > 0; step >>= 1 ) {
        if ( sol - step > 0 && ind( sol - step ) >= k ) {
            sol -= step;
        }
    }
    fout << sol << "\n";
    fin.close();
    fout.close();
    return 0;
}