#include <stdio.h>   
  
long long n, p, sum, prod = 1, nr = 0;   
int prim[20000], v[128];   
  
void go(int pos, long long x)   
{   
    if (prod > x)   
        return;   
  
    if (pos > v[0]) {   
        if (nr > 0) {   
            if (nr % 2)   
                sum -= x / prod;   
            else   
                sum += x / prod;   
        }   
    } else {   
        go(pos + 1, x);   
        prod = (long long)prod * v[pos];   
        ++nr;   
        go(pos + 1, x);   
        --nr;   
        prod = (long long)prod / v[pos];   
    }   
}   
  
long long solve(long long x)   
{   
    sum = x;   
  
    go(1, x);   
  
    return sum;   
}   
  
int main()   
{   
    freopen("frac.in", "r", stdin);   
    freopen("frac.out", "w", stdout);   
  
    scanf("%lld %lld", &n, &p);   
  
    for (int i = 2; i <= 150000; ++i) {   
        int ok = 1;   
  
        for (int j = 1; j <= prim[0] && prim[j] * prim[j] <= i && ok; ++j)   
            if (i % prim[j] == 0)   
                ok = 0;   
  
        if (ok)   
            prim[++prim[0]] = i;   
    }   
  
    long long tmp = n;   
  
    for (int i = 1; (long long)prim[i] * prim[i] <= n; ++i)   
        if (tmp % prim[i] == 0) {   
            v[++v[0]] = prim[i];   
  
            while (tmp % prim[i] == 0)   
                tmp = (long long)tmp / prim[i];   
        }   
  
    if (tmp > 1)   
        v[++v[0]] = tmp;   
  
    long long step = ((long long)1) << 61, crt;   
  
    for (crt = 0; step; step = (long long)step / 2)   
        if (solve((long long)crt + step) < p)   
            crt = (long long)crt + step;   
  
    printf("%lld\n", (long long)crt + 1);   
  
    return 0;   
}