#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
using namespace std;

#define inf (1LL << 62)

long long N, P;
long long sol;
vector<long long> Pr;

long long getVal(long long X)
{
    long long ans = 0;
    int lim = Pr.size();
    for(int conf = 0; conf < (1 << lim); conf ++)
    {
        long long now = 1;
        int sign = 1;
        for(long long i = 0; i < lim; i++)
            if(conf & (1 << i))
                now *= Pr[i], sign *= (-1);
        ans += sign * X / now;
    }
    return ans;
}

int main()
{
    freopen("frac.in", "r", stdin);
    freopen("frac.out", "w", stdout);
    scanf("%lld %lld", &N, &P);
    for(long long i = 2; i * i <= N; i++)
    {
        if(N % i == 0)
            Pr.push_back(i);
        while(N % i == 0)
            N /= i;
    }
    if(N > 1) Pr.push_back(N);
    long long left = 1, right = inf;
    while(left <= right)
    {
        long long mid = (left + right) / 2;
        if(getVal(mid) >= P)
            sol = mid, right = mid - 1;
        else left = mid + 1;
    }
    printf("%lld\n", sol);
    return 0;
}