#include <fstream>

using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
int_fast64_t in,sf,n,p2,mij,rasp,v[31],i,nr,ans;
void bkt(int poz,unsigned long long p,int m)
{
    if(poz>nr)
    {
        if(p==1)
        {
            return;
        }
        if(m%2==0)
        {
            rasp-=mij/p;
            //g<<mij<<" "<<poz<<" "<<p<<" "<<m<<" "<<rasp<<'\n';
        }
        else
        {
            rasp+=mij/p;
            //g<<mij<<" "<<poz<<" "<<p<<" "<<m<<" "<<rasp<<'\n';
        }
        return;
    }
    bkt(poz+1,p*v[poz],m+1);
    bkt(poz+1,p,m);
}
int main()
{
    f>>n>>p2;
    i=2;
    while(i*i<=n)
    {
        if(n%i==0)
        {
            nr++;
            v[nr]=i;
        }
        while(n%i==0)
        {
            n/=i;
        }
        i++;
    }
    if(n!=1)
    {
        nr++;
        v[nr]=n;
    }
    in=1;
    sf=100000000000000000;
    //sf=15;
    while(in<=sf)
    {
        mij=in+sf;
        mij/=2;
        rasp=0;
        bkt(1,1,0);
        rasp=mij-rasp;
        if(rasp<p2)
        {
            in=mij+1;
        }
        else if(rasp>p2)
        {
            sf=mij-1;
        }
        else
        {
            sf=mij-1;
            ans=mij;
        }
        //g<<in<<" "<<sf<<" "<<rasp<<'\n';
    }
    g<<ans<<'\n';
    return 0;
}