#include<fstream>

using namespace std;

ifstream f("gfact.in");
ofstream g("gfact.out");

typedef long long int64;

int64 p,q,k,pr[50],powers[50],i,step,maxt,j;

int64 calc(int64 a,int64 pr)
{
    int64 r=0;
    while(a)
        r+=a/pr,a/=pr;
    return r;
}

int main()
{
    f>>p>>q;
    for(i=2;i*i<=p;++i)
        if(p%i==0)
        {
            pr[++k]=i;
            while(p%i==0)
                p/=i,++powers[k];
        }
    if(p>1)
        pr[++k]=p,powers[k]=1;
    for(i=1;i<=k;++i)
        powers[i]*=q;
    for(i=1;i<=k;++i)
    {
        step=1LL<<62;
        for(j=0;step;step>>=1)
            if(calc(j+step,pr[i])<powers[i])
                j+=step;
        j+=pr[i]-j%pr[i];
        if(j>maxt)
            maxt=j;
    }

    g<<maxt<<"\n";

    f.close();
    g.close();

    return 0;
}