#include <stdio.h>
#define LMax 110010
#define PMax 11010
typedef unsigned long long ll;
const char IN[]="frac.in",OUT[]="frac.out";
  
ll N,P;
int p[PMax];
int a[PMax];
  
void ciur()
{
    int i,j;
    static bool b[LMax];
    for (i=2;i<LMax;++i) if (!b[i])
    {
        p[++p[0]]=i;
        if (i<333)
        for (j=i*i;j<LMax;j+=i) b[j]=true;
    }
}
  
void prepare(ll A)
{
    int i;
    for (i=1;p[i]*p[i]<=A;++i) if (A%p[i]==0)
    {
        a[++a[0]]=p[i];
        while (A%p[i]==0) A/=p[i];
    }
    if (A!=0) a[++a[0]]=A;
}
  
ll number(ll L)
{
    int i,mask,cnt;
    ll c,ret=0;
  
    for (mask=1;mask<(1<<a[0]);++mask)
    {
        c=1;cnt=0;
        for (i=0;i<a[0] && c<=L;++i) if ((1<<i)&mask)
            c*=a[i+1],++cnt;
        if (cnt&1)
            ret+=L/c;
        else
            ret-=L/c;
    }
    return L-ret;
}
  
ll search(ll L)
{
    ll i,step;
    step=1LL<<61;
    for (i=L;step;step>>=1)
        if (i-step>0 && number(i-step)>=P)
            i-=step;
    return i;
}
  
int main()
{
    int i;
    freopen(IN,"r",stdin);
    scanf("%lld%lld",&N,&P);
    fclose(stdin);
  
    ciur();
    prepare(N);
  
    freopen(OUT,"w",stdout);
    printf("%lld\n",search(1LL<<61));
    fclose(stdout);
  
    return 0;
}