#include<cstdio>

using namespace std;

typedef long long luu;

luu k;

inline luu nr(luu m)
{
    luu aux=0,pr=k;
    while(m/pr)
    {
        aux+=(m/pr);
        pr*=k;
    }
    return aux;
}

inline luu bs(luu val)
{
    int i,step,n=2*val*k;
    for (step=1;step<n;step<<=1);
    for (i=n;step;step>>=1)
        if (i>step&&nr(i-step)>=val)
           i-=step;
    return i;
}

int main()
{
    luu p,q,r,sol=0,aux;
    freopen("gfact.in","r",stdin);
    freopen("gfact.out","w",stdout);
    scanf("%lld %lld",&p,&q);
    for(k=2;k*k<=p;++k)
        if (p%k==0)
        {
            r=0;
            while(p%k==0)
            {
                ++r;
                p/=k;
            }
            r=r*q;
            aux=bs(r);
            if (aux>sol)
                sol=aux;
        }
    if(p>1)
	{
	    k=p;
	    r=q;
		aux=bs(r);
		if (aux>sol)
            sol=aux;
	}
    printf("%lld\n",sol);
    return 0;
}