#include <cstdio>

#define LMAX 16

long long N, P;
int p[LMAX], fact[LMAX];
long long sol, MAX = 1LL<<61, nr;

void factors(long long n)
{
    int d = 2, ok;
    while(n > 1)
    {
        ok = 0;
        while(n%d == 0)
        {
            n /= d;
            ok = 1;
        }
        if(ok)
        {
            fact[++fact[0]] = d;
        }
        d++;
    }
}

int count()
{
    int nr = 0;
    for(int i=0;i<fact[0];++i)
    {
        nr += p[i];
    }
    return nr;
}

int back(int k, long long n)
{
    if(k == fact[0])
    {
        int f = -1;
        if(count() % 2 == 1)
            f = 1;
        long long num = 1, ok = 0;
        for(int i=1;i<=fact[0];++i)
        {

            if(p[i-1])
            {
                num *= fact[i];
                ok = 1;
            }
        }
        if(ok)
            nr += f*(n/num);
    }
    else
    {
        for(int i=0;i<=1;++i)
        {
            p[k] = i;
            back(k+1,n);
        }
    }
}

long long nrf(long long n) //numarul de fractii cu numitorul <= n
{
    nr = 0;

    back(0, n);

    return n - nr;
}

int main()
{
    freopen("frac.in", "r", stdin);
    freopen("frac.out", "w", stdout);

    scanf("%lld %lld", &N, &P);

    long long st=1, dr=MAX, sol, m;

    factors(N);

    while(st <= dr)
    {
        m = (st+dr)/2;

        if(nrf(m) >= P)
        {
            dr = m-1;
            sol = m;
        }
        else
        {
            st = m+1;
        }
    }

    printf("%lld\n", sol);

    return 0;
}