#include<stdio.h>
#define ll long long

ll max;
int p,q,f[101],e[101],nr;
ll put(ll fact, int p)
{
    ll r = 0;
    while (fact>0)
    {
        r += fact/p;
        fact /= p;
    }
    return r;
}

ll caut(int poz)
{
    ll st=1;ll dr=((ll)1<<60); ll sol=-1;
    ll m;
    while(st<=dr)
    {
        m=(st+dr)/2;
        ll nr = put(m, f[poz]);
        if(nr>=e[poz])
            sol=m, dr=m-1;
        else
            st=m+1;
    }
    return sol;
}
int main ()
{

    ll b;
    int pr,cp,i;
    freopen("gfact.in","r",stdin);
    freopen("gfact.out","w",stdout);
    scanf("%d%d",&p,&q);
    pr=2; cp=p;
    while(pr*pr<=p && cp>1)
    {
        if(cp%pr==0)
        {
            nr++;
            f[nr]=pr;
        }
        while(cp%pr==0)
        {
            cp=cp/pr;
            e[nr]++;
        }

        pr++;
    }
    if(cp>1)
        f[++nr]=cp,e[nr]=1;
    for(i=1;i<=nr;i++)
        e[nr]*=q;
    for(i=1;i<=nr;i++)
    {
        b=caut(i);
        if(b>max)
            max=b;
    }
    printf("%lld\n",max);
    return 0;
}