#include<fstream>

using namespace std;

ifstream f("frac.in");
ofstream g("frac.out");

typedef long long int64;

int64 n,p,primes[20],methods[1200],values[1200],i,k,r,x,y,m,j;

int64 go(int64 x)
{
    int64 i,pos=0;
    for(i=1;i<=r;++i)
        if(values[i]&1)
            pos+=x/methods[i];
        else
            pos-=x/methods[i];
    return x-pos;
}

int main()
{
    f>>n>>p;
    for(i=2;i*i<=n;++i)
        if(n%i==0)
        {
            while(n%i==0)
                n/=i;
            primes[++k]=i;
        }
    if(n>1)
        primes[++k]=n;

    r=(1<<k)-1;
    for(;r;--r)
    {
        methods[r]=1;
        values[r]=0;
        values[r]=0;
        for(i=0;(1<<i)<=r;++i)
            if((1<<i)&r)
                methods[r]*=primes[i+1],++values[r];
    }

    r=(1<<k)-1;

    x=1;
    y=1LL<<61;

    while(x<=y)
    {
        m=(y+x)>>1;
        i=go(m);
        if(i<p)
            x=m+1;
        else
            if(i>p)
                y=m-1;
            else
            {
                for(j=1;j<=k;++j)
                    if(m%primes[j]==0)
                        break;
                if(j>k)
                    break;
                else
                    y=m-1;
            }
    }

    g<<m<<"\n";

    f.close();
    g.close();

    return 0;
}