#include <fstream>

using namespace std;
long long k,x,i,j,t,p,S,nr,w,m,s,d,Min,v[120000];
bool e[120000],u[120000],OK;
const long long c=110000;
int main()
{
    ifstream f("frac.in");
    ofstream g("frac.out");

    for(i=2;i*i<=c;i++)
    if(!e[i])
    for(j=i*i;j<=c;j=j+i)
    e[j]=1;

    f>>x>>k;

    for(i=2;i*i<=x;i++)
    if(!e[i] && x%i==0)
    v[++t]=i;
    for(i=1;i<=t;i++)
    while(x%v[i]==0)
    x/=v[i];
    if(x!=1)
    v[++t]=x;

    s=0; d=Min=1000000000000000000;
    while(s<=d)
    {
        m=(s+d)/2;
        if(m==5)
        OK=0;
        while(!OK)
        {
            OK=1; p=1; S=1; nr=0;
        while(p<=t)
        {
            if(OK)
            {
                if(u[p])
                u[p]=0;
                else
                {
                    OK=0;
                    u[p]=1;
                    S*=v[p];
                    nr++;
                }
            }
            else
            {
                if(u[p])
                {
                    S*=v[p];
                    nr++;
                }
            }
            p++;
        }
        if(nr%2)
        w-=m/S;
        else
        w+=m/S;
        }
        if(w==k)
        {
            if(m<Min)
            Min=m;
            d=m-1;
        }
        if(w>k)
        d=m-1;
        if(w<k)
        s=m+1;
        for(i=1;i<=t;i++)
        u[i]=0;
        OK=0; w=0;
    }
    g<<Min;


    return 0;
}