#include <fstream>
#include <vector>
#define VAL 109545
#define DIVIZ 45
#define LL long long

using namespace std;

ifstream fin("frac.in");
ofstream fout("frac.out");

int K;
LL N, P;
LL DIV[DIVIZ];
bool ok[VAL];
vector<LL> prim;
vector<LL> :: iterator it;

void Sieve()
{
    LL i, j;
    for (i=2; i<VAL; i++)
    {
        if (ok[i]==false)
        {
            prim.push_back(i);
            for (j=i*i; j<VAL; j+=i)
              ok[j]=true;
        }
    }
}

void Decompose(LL N)
{
    for (it=prim.begin(); it!=prim.end() && (*it)*(*it)<=N; it++)
    {
        if (N % (*it)==0)
        {
            DIV[K++]=*it;
            while (N % (*it)==0)
              N/=*it;
        }
        if (N==1)
          break;
    }
    if (N>1)
      DIV[K++]=*it;
}

LL Verify(LL X)
{
    int i, j, cnt;
    LL ANS=0, P;
    for (i=1; i<(1 << K); i++)
    {
        P=1;
        cnt=0;
        for (j=0; j<K; j++)
        {
            if ((i & (1 << j))!=0)
            {
                cnt++;
                P*=DIV[j];
            }
        }
        if (cnt % 2==1)
          ANS+=X / P;
        else
          ANS-=X / P;
    }
    return X-ANS;
}

LL Binary_Search()
{
    LL be=1, en=1LL << 61;
    LL mid, ans=0;
    while (be<=en)
    {
        mid=(be+en) / 2;
        if (Verify(mid)>=P)
        {
            ans=mid;
            en=mid-1;
        }
        else
          be=mid+1;
    }
    return ans;
}

int main()
{
    fin >> N >> P;
    Sieve();
    Decompose(N);
    fout << Binary_Search() << '\n';
    fin.close();
    fout.close();
    return 0;
}