#include<fstream>
#include<cmath>
using namespace std;
ifstream in("frac.in");
ofstream out("frac.out");
long long b,p,n,i,j,w[25],v[25],st,dr,mid,d,sum,g,f,s;
int main(){
    in >> b >> p;
    g = b;
    for( i = 2; i*i <= g; i ++ ){
        if( b % i == 0 ){
            v[++n] = i;
            while( b % i == 0 ){
                b/=i;
            }
        }
    }
    if( b > 1 ){
        v[++n] = b;
        b =1;
    }
    for( st = 1, dr = 1e18; st <= dr; ){
        mid = st + ( dr - st )/2;
        for( i = 0; i <= n; i ++ ){
            w[i] = 0;
        }
        sum = 0;
        while( w[0] == 0 ){
            i = n;
            while( w[i] == 1 && i > 0 ){
                w[i] = 0;
                i--;
            }
            w[i] = 1;
            f = 1;
            d = 0;
            if( w[0] == 1 ){
                break;
            }
            for( j = 1; j <= n; j ++ ){
                if( w[j] == 1 ){
                    f *= v[j];
                    d ++;
                }
            }
            if( d % 2 == 0 ){
                sum -= mid/f;
            }
            else{
                sum += mid/f;
            }
        }
        if( mid - sum < p ){
            st = mid + 1;
        }
        else{
            dr = mid - 1;
        }
    }
    out<<st;
    return 0;
}