#include <iostream>
#include <fstream>
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
bool ok[1000005];
int pr[80005],k=0,mofo=0;
long long a,b,d[1005],vaar1=0;

void prim()
{
    int i,j,maxxx=1000000;
    for(i=2; i<=maxxx; i++)
    {
        if (!ok[i])
        {
            k++;
            pr[k]=i;
            for(j=i+i; j<=maxxx; j+=i)
                ok[j]=1;
        }
    }
}

void prog(long long x)
{
    int i;
    mofo=0;
    for(i=1; i<=k && x>1; i++)
    {
        if (x%pr[i]==0)
        {
            mofo++;
            d[mofo]=pr[i];
            while(x%pr[i]==0) x/=pr[i];
        }
        if (1LL*pr[i]*pr[i]>1LL*x) break;
    }
    if (x>1)
    {
        mofo++;
        d[mofo]=1LL*x;
    }

}

long long funn2(long long lim)
{
    int i,j,num=0;
    long long mult=0,sol=0;

    for(i=1; i<(1<<mofo); i++)
    {
        num=0;
        mult=1;
        for(j=0; j<mofo; j++)
            if (i&(1<<j))
            {
                mult*=1LL*d[j+1];
                num++;
            }
        if (num%2==1) sol+=1LL*(lim/mult);
        else sol-=1LL*(lim/mult);
    }

    return 1LL*(lim-sol);
}

void Binary()
{
    long long st=1,dr=(1LL<<61),mid=0;
    while(1LL*st<1LL*dr)
    {
        mid=1LL*(st+dr)/2;
        if (1LL*funn2(mid)>=1LL*vaar1) dr=1LL*mid;
        else st=1LL*(mid+1);
    }
    g<<1LL*st;
}
int main()
{
    int t;
    prim();

    f>>b>>vaar1;
    prog(b);
    Binary();
    //cout<<funn2(10000000000);

    return 0;
}