#include<cstdio>
#include<math.h>
using namespace std;
int f[15],nr,nr1,nr2,v1[15],poz=1,st[15];
long long q=1;
struct Doica
{
    long long x;
    int y;
};

Doica v[5000];
void bkt(int x)
{
    for(int i=st[x-1]+1;i<=nr;++i)
    {
            q*=v1[i];
            v[++nr2].x=q;
            f[i]=1;
            nr1++;
            v[nr2].y=nr1;
            poz++;
            st[x]=i;
            bkt(x+1);
            q/=v1[i];
            f[i]=0;
            nr1--;
    }
}

long long cmmdc(long long a,long long b)
{
    while(b!=0)
    {
        long long r=a%b;
        a=b;
        b=r;
    }
    return a;
}

int main()
{
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    long long n,p,st=1,dr=(1LL<<61),med,nr3,x;
    int b=3,ok=0,i;
    scanf("%lld%lld",&n,&p);
    x=n;
    if(n%2==0)
    {
        v1[++nr]=2;
        while(n%2==0)
        {
            n/=2;
        }
    }
    while(b*b<=n)
    {
        if(n%b==0)
        {
            v1[++nr]=b;
            while(n%b==0)
            {
                n/=b;
            }
        }
        b+=2;
    }
    if(n>1)
        v1[++nr]=n;
    bkt(1);
    while(ok==0)
    {
        med=st+((dr-st)>>1);
        nr3=0;
        for(i=1;i<=nr2;++i)
        {
            if(v[i].y%2==0)
                nr3-=(med/v[i].x);
            else
                nr3+=(med/v[i].x);
        }
        if(med-nr3==p)
            {
                if(cmmdc(med,x)==1)
                {
                    printf("%lld\n",med);
                    ok=1;
                }
                else
                    dr=med;
            }
            else
            {
                if(med-nr3<p)
                    st=med;
                else
                    dr=med;
            }
    }
    return 0;
}