#include<fstream>
#include<cmath>
#include<cassert>

using namespace std;

long long n, p;
int nd, cod, nr, s[20];
long long divz[20], result, nrdiv[20], prod;
ofstream g("frac.out");  

void back(int k, long long m) {
    for (int i = 0; i <= 1; i++) {
        s[k] = i;
        if (i == 1) {
            nr++;
            prod *= divz[k];
        }
        if (k == nd) {
            if (nr % 2 == 1)
                result -= m/prod;
            else    
                result += m/prod;  
        }
        else 
            back(k+1, m);
        if (i == 1) {
            nr--;
            prod /= divz[k];
        }
    }    
}

long long trym(long long m) {
    for (int i = 1; i <= nd; i++)
        nrdiv[i] = m/divz[i];        
    
    result = 0;
    prod = 1;
    nr = 0;
    back(1, m);
    cod = 1;
    for (int i = 1; i <= nd; i++)
        if (m % divz[i] == 0) {
            cod = 0;
            break;
        }
    return result; 
}

long long bsearch(long long pr, long long u) {
    long long m, x;
    while (pr <= u) {
        m = (pr+u)/2;
        long long t;
        t = trym(m);
        if ( (t > p) || (t == p && cod == 0) )
            u = m-1;
        else    
            if (t < p)
                pr = m+1; 
            else 
                return m; 
    }    
}

int main() {
    ifstream f("frac.in");
     
    f >> n >> p;
    assert(n > 1);
    
    long long nn = n;
    long long i;
    for (i = 2; i <= sqrt(nn); i++)
        if (n%i == 0) {
            nd++;
            divz[nd] = i;
            while (n%i == 0) 
                n = n/i;
        }
        
    if (nd == 0) {
        nd++;
        divz[nd] = n;
    }
    
    long long x = (long long) 1 << 61;  
    long long result = bsearch(1, x);
    
    g << result << '\n';
    
    return 0;
}