#include <cstdio>
#include <climits>
#define BIT(x) (1<<(x))

using namespace std;
typedef long long llong;

llong n, p;
llong fact[30];
int lfact;

void genFact(llong a)
{
    if(a % 2 == 0)
    {
        fact[lfact++] = 2;
        while(a % 2 == 0) a /= 2;
    }
    for(int i = 3; a != 1; i++)
    {
        if(a % i == 0)
        {
            fact[lfact++] = i;
            while(a % i == 0) a /= i;
        }
    }
}

llong getIndex(llong a)
{
    llong i, j, r, rez = 0;
    int nb;
    for(i = 0; i < BIT(lfact); i++)
    {
        r = 1;
        nb = 0;
        for(j = 0; j < lfact; j++)
        {
            if(i & BIT(j))
            {
                nb++;
                r *= fact[j];
            }
        }
        if(nb % 2 == 0) rez += a / r;
        else rez -= a / r;
    }
    return rez;
}

int main()
{
    llong st, dr, mid, aux;
    freopen("frac.in", "r", stdin);
    freopen("frac.out", "w", stdout);
    scanf("%lld%lld", &n, &p);
    genFact(n);
    st = 1;
    dr = LONG_LONG_MAX;
    while(st < dr)
    {
        mid = st + (dr - st) / 2;
        aux = getIndex(mid);
        if(aux < p) st = mid + 1;
        else dr = mid;
    }
    mid = st + (dr - st) / 2;
    printf("%lld", mid);
    return 0;
}