#include <bits/stdc++.h>
using namespace std;
ifstream fin ("frac.in");
ofstream fout("frac.out");
long long val,best,mij,n,k,d,a[30];
void bkt(long long poz,long long cnt,long long produs,long long x)
{
    if(poz>a[0])
    {
        if(cnt==0)
            return;
        if(cnt%2==1)
            val=val+x/produs;
        else val=val-x/produs;
        return;
    }
    bkt(poz+1,cnt,produs,x);
    bkt(poz+1,cnt+1,produs*a[poz],x);
}
signed main()
{
    fin>>n>>k;
    d=2;
    while(n!=1)
    {
        if(n%d==0)
        {
            a[++a[0]]=d;
            while(n%d==0)
                n/=d;
        }
        d++;
        if(d%2==0)
            d++;
        if(d*d>n)
            d=n;
    }
    long long st=1,dr=LLONG_MAX;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        val=0;
        bkt(1,0,1,mij);
        if(mij-val>=k)
        {
            best=mij;
            dr=mij-1;
        }
        else st=mij+1;
    }
    fout<<best;
    return 0;
}