#include <cstdio>
using namespace std;
int f[15],e[15];
inline long long legendre(long long n,long long p)
{
    long long s=0;
    while(n)
    {
        s=s+n/p;
        n=n/p;
    }
    return s;
}
inline int bs(int poz)
{
    long long st,dr,med,nr,last=-1;
    st=1;
    dr=(1LL<<60)-1;
    while(st<=dr)
    {
        med=st+((dr-st)>>1);
        nr=legendre(med,f[poz]);
        if(nr>=e[poz])
        {
            dr=med-1;
            last=med;
        }
        else
            st=med+1;
    }
}
int main()
{
    freopen("gfact.in","r",stdin);
    freopen("gfact.out","w",stdout);
    int p,q,d,ex,cnt=0,i;
    long long b,max=0;
    scanf("%d%d",&p,&q);
    //Descompunerea in factori primi a lui p
    d=2;
    while(1LL*d*d<=p && p>1)
    {
        ex=0;
        while(p%d==0)
        {
            p=p/d;
            ex++;
        }
        if(ex>0)
        {
            f[++cnt]=d;
            e[cnt]=ex*q;
        }
        d++;
    }
    if(p>1)
    {
        f[++cnt]=p;
        e[cnt]=q;
    }
    b=1;
    for(i=1;i<=cnt;i++)
    {
        b=bs(i);
        if(b>max)
            max=b;
    }
    printf("%lld\n",max);
    return 0;
}