#include<stdio.h>
02.long long n,p,nrp,prim[1<<4],prod[1<<10];
03.void pinex()
{
    long long i,j,x,p;
    for(i=0 ; i<(1<<nrp) ; ++i)
    {
       p=1;
       x=i;
       for(j=0 ; x ; ++j,x>>=1) if(x&1) p *= -prim[j];
        prod[i]=p;
    }
}
.long long calc(long long x)
{
    int i;
    long long s=0;
    for(i=0;i<(1<<nrp);++i)
        s+=x/prod[i];
    return s;
}
.int main()
{
    long long i,pas=(long long)1<<61;
   freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    scanf("%lld%lld",&n,&p);
   for(i=2;i*i<=n;++i)
       if(n%i==0)
       {
            while(n%i==0) n/=i;
            prim[nrp++]=i;
       }
    if(n!=1) prim[nrp++]=n;
   pinex();
    for(i=0 ; pas ; pas>>=1) if(calc(i+pas)<p) i+=pas;
printf("%lld\n",++i);
    return 0;
}