#include <cstdio>
#include <algorithm>

using namespace std;
#define ll long long

ll primes[30], cp;

void desc(ll n){
    cp = 0;
    if(n%2 == 0){
        primes[++cp] = 2;
        while(n%2 == 0){
            n /= 2;
        }
    }
    for(int i = 3;i*i <= n;i += 2){
        if(n%i == 0){
            primes[++cp] = i;
            while(n%i == 0){
                n /= i;
            }
        }
    }
    if(n != 1){
        primes[++cp] = n;
    }
}

ll solve(ll A){
    int i,j;
    ll sol = A;
    for(i = 1;i < (1 << cp);i++){
        int nr = 0;
        ll prod = 1;
        for(j = 0;j < cp;j++){
            if(i & (1 << j)){
                prod *= primes[j + 1];
                nr++;
            }
        }
        if(nr%2 == 1){
            sol -= A/prod;
        }else{
            sol += A/prod;
        }
    }
    return sol;
}

ll binarySearch(ll lf, ll rg, ll p){
    ll i,step;
    for(step = 1;step <= rg;step <<= 1);
    for(i = lf - 1;step;step >>= 1){
        if(i + step <= rg && solve(i + step) <= p){
            i += step;
        }
    }
    return i;
}

int main(){
    freopen("frac.in", "r", stdin);
    freopen("frac.out", "w", stdout);
    ll n,p;
    scanf("%lld %lld", &n, &p);
    desc(n);
    printf("%lld\n", binarySearch(1, 1LL<<61, p - 1) + 1);
    return 0;
}