#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> dv;long long CN;
long long calcule(long long a)
{
    long long i,nr,x[100],p,s=0,aux;
    fill(x,x+dv.size()+1,0);
    ///nu stiu de ce nu merge pe variabila simpla, asa ca fac baza 2 pe vector
    while(x[0]!=1)
    {
        i=dv.size();
        while(x[i]==1) {x[i]=0;i--;}
        if(i==0) break;
        x[i]=p=1;nr=0;
        for(i=1;i<=(int)dv.size();i++)
            if(x[i]==1)
            {
                nr++;
                p*=dv[i-1];
            }
        if(nr%2==0) s-=a/p;
        else s+=a/p;
    }
    return a-s;
}
int main()
{
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    long long N,P,last,st,dr,med,x;
    scanf("%lld%lld",&N,&P);CN=N;
    long long lim,d;
    lim=(long long)sqrt(1.0*N);d=2;
    while(d<=lim && N>1)
    {
        if(N%d==0) dv.push_back(d);
        while(N%d==0) N/=d;
        d++;
    }
    if(N>1) dv.push_back(d);
    st=0;dr=(1LL<<61);med=0;
    while(st+1<dr)
    {
          med=(st+dr)/2;x=calcule(med);
          if(x==P)
             last=med;
          if(x>=P) dr=med;
          else st=med;
    }
    printf("%lld\n",last);
    return 0;
}