#include<stdio.h>
#define Dm (1<<18)
#define Km 10
typedef long long ll;
typedef unsigned long long ull;
int Odd[1<<Km],k;
ll D[Dm],Prod[1<<Km],Pf[Km],n,p;

void read()
{
    freopen("frac.in","r",stdin);
    scanf("%lld%lld",&n,&p);
}

ll coprime(ull m)
{
    int i;
    ll ans=0;

    for(i=0;i<1<<k;++i)
        if(Odd[i])
            ans-=m/Prod[i];
        else
            ans+=m/Prod[i];
    return ans;
}

ull solve()
{
    int i,j,nd=0;
    ull l,r,m;

    for(i=1;(ll)i*i<=n;++i)
        if(n%i==0)
            D[++nd]=i;
    for(i=nd;i;--i)
        D[++nd]=n/D[i];
    for(i=2;i<=nd;++i)
        if(n%D[i]==0)
        {
            Pf[k++]=D[i];
            while(n%D[i]==0)
                n/=D[i];
        }
    for(i=0;i<1<<k;++i)
    {
        Prod[i]=1; Odd[i]=0;
        for(j=0;j<k;++j)
            if(i&1<<j)
            {
                Prod[i]*=Pf[j];
                ++Odd[i];
            }
        Odd[i]&=1;
    }

    l=1; r=1llu<<61;
    while(l<r)
    {
        m=(l+r)>>1;
        if(coprime(m)<p)
            l=m+1;
        else
            r=m;
    }
    return l;
}

void write(ull ans)
{
    freopen("frac.out","w",stdout);
    printf("%llu\n",ans);
}

int main()
{
    read();
    write(solve());
    return 0;
}