#include<cstdio>

const int nmax=110000;

long long n,p,st,dr,fact[1001],aux,nrtot,sol,prod,nr,rez,i,j,nrfact,mij;

int main()
{
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    scanf("%lld%lld",&n,&p);
    aux=n;
    for(i=2;i<=aux;i++)
    {
        if(aux%i==0)
        {
            fact[++nrfact]=i;
            while(!(aux%i))
                aux/=i;
        }
    }
    nrtot=1<<nrfact;
    st=1;
    dr=(long long)1<<61;
    //caut binar
    while(st<=dr)
    {
        mij=(st+dr)/2;
        sol=0;
        //pinex
        for(i=1;i<nrtot;i++)
        {
            nr=0;
            prod=1;
            for(j=0;j<nrfact;j++)
            {
                if(((1<<j)&i)!=0)
                {
                    nr++;
                    prod*=fact[j+1];
                }
            }
            if(nr%2)
                nr=1;
            else
                nr=-1;
            sol+=1LL*nr*(mij/prod);
        }
        if(mij-sol<p)
            st=mij+1;
        else
        {
            dr=mij-1;
            rez=mij;
        }
    }
    printf("%lld",rez);
}