#include <cstdio>
#include <vector>
#include <climits>
#define LL long long
#define pb push_back

using namespace std;

LL n,p;
vector <LL> d;
LL st=1;
LL dr=LLONG_MAX;
inline LL pozitie(LL m);

inline void divizori(LL n)
{
    LL i;
    for (i=2;i*i<=n && n;++i)
    {
        bool ok;
        while (n%i)
            n/=i, ok=true;

        if (ok) d.pb(i);
    }
}

inline void cb()
{
    LL m;
    for (m=(st+dr)>>1;st<=dr;m=(st+dr)>>1)
    {
        LL poz=pozitie(m);
        if (poz>=p) dr=m-1;
         else st=m+1;
    }

    printf("%lld\n", st);
}

inline LL pozitie(LL m)
{
    LL i,j;
    LL val,crt,nr=0;
    for (i=1;i<(1<<d.size());++i)
    {
        val=m; crt=0;
        for (j=0;j<d.size();++j)
            if (i>>j&1) ++crt, val/=d[j];

        if (crt&1)
        {
            nr+=val;
            continue;
        }
        nr-=val;
    }

    return m-nr;
}

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

    scanf("%lld %lld", &n, &p);

    divizori(n);

    cb();

    return 0;
}