#include <cstdio>
#include <algorithm>
using namespace std;
FILE *f = fopen( "frac.in" , "r" );
FILE *g = fopen( "frac.out" , "w" );
long long N;
long long P;
vector<long long> D;
long long pinex(long long A){
    long long rez = 0;
    for(int conf = 0;conf < 1 << D.size();conf++){
        int sgn = 1;
        long long tmp = 1;
        for(int i = 0;i < D.size();i++){
            if((conf >> i) & 1){
                tmp *= D[i];
                sgn *= -1;
            }
        }
        rez += sgn * (A / tmp);
    }
    return rez;
}
int main()
{
    fscanf(f,"%lld %lld",&N,&P);
    for(long long d = 2;d * d <= N;d++){
        if(N % d == 0){
            D.push_back( d );
            while(N % d == 0){
                N /= d;
            }
        }
    }
    if(N != 1){
        D.push_back(N);
    }
    long long st = 0,dr = (1LL << 61);
    while( dr - st > 1 ){
        long long mid = (st + dr) / 2;
        if( pinex( mid ) >= P){
            dr = mid;
        }
        else {
            st = mid;
        }
    }
    fprintf(g,"%lld",dr);
    fclose(f);
    fclose(g);
    return 0;
}