#include <fstream>
#include <bitset>
#include <cmath>
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
unsigned long long n,p,ve[25],st,dr,m,nr,nr1,best;
int i,j,lim,u,c,l;
bitset <110001> prim;
int main()
{
    f>>n>>p;
    c=sqrt(n);
    l=0;
    if (n%2==0)
    {
        ve[++l]=2;
        while(n%2==0)
            n=n/2;
    }
    for (i=3;i<=c;i+=2)
        if (prim[i]==false)
        {
            j=i*i;
            if (j/i==i)
                for (j=i*i;j<=c;j+=i)
                prim[j]=true;
            if (n%i==0)
            {
              ve[++l]=i;
              while(n%i==0)
                n=n/i;
            }
        }
    if (n>1)
        ve[++l]=n;
    st=1,dr=1ll<<61;
    while(st<=dr)
    {
        m=(st+dr)>>1;
        nr=0;
        lim=1<<l;
        for (i=1;i<lim;i++)
        {
         nr1=m;
            u=0;
            for (j=1;j<=l;j++)
            if (i & (1<<(j-1)))
            u++,nr1=nr1/ve[j];

        if (u%2==0) nr-=nr1;
        else nr+=nr1;
        }
        if (m-nr>=p) best=m,dr=m-1;
        else st=m+1;
    }
    g<<best<<'\n';
    return 0;
}