#include <cstdio>
#include <cmath>
#include <bitset>
#include <vector>

using namespace std;

typedef long long LL;

const LL MAX_N = 12e9;

LL n,p;
bitset<110000> is_prime;
vector<int> primes;
vector<int> factors;

void sieve(){
    primes.push_back(2);
    const int lim = sqrt(MAX_N);
    for(int i = 3 ; i <= lim ; i += 2){
        if(is_prime[i]){
            primes.push_back(i);
            for(int j = i * i ; j <= lim ; j += 2 * i){
                is_prime[j] = false;
            }
        }
    }
}

void factorise(const LL what){
    LL now = what;
    for(unsigned int i = 0 ; i < primes.size() && primes[i] * primes[i] <= now ; ++ i){
        if(now % primes[i] == 0){
            factors.push_back(primes[i]);
            while(now % primes[i] == 0)
                now /= primes[i];
        }
    }
    if(now > 1)
        factors.push_back(now);
}

LL sol, limit;

void back(const int at,const int included, const LL prod){
    if(unsigned(at) == factors.size()){
        const int sign = -2 * (included % 2) + 1;
        sol += (limit / prod) * sign;
    } else {
        back(at + 1, included, prod);
        back(at + 1, included + 1, prod * factors[at]);
    }
}

LL before(const LL lim){
    sol = 0;
    limit = lim;
    back(0, 0, 1);
    return sol;
}

LL bsearch(const LL what){
    LL step = 1LL << 61, i = step;
    for(; step > 0 ; step >>= 1){
        if(before(i - step) >= what)
            i -= step;
    }
    return i;
}

int main(){
    sieve();
    freopen("frac.in" , "r", stdin);
    scanf("%lld %lld", &n, &p);
    factorise(n);
    freopen("frac.out", "w", stdout);
    printf("%lld\n", bsearch(p));
}