#include <fstream>

using namespace std;
ifstream f ("gfact.in");
ofstream g ("gfact.out");
int p,q,exp,d;
unsigned long long i,step,Max;
int verif (int n, int x)
{
    int nr=0;
    while (n>=x)
    {
        nr+=n/x;
        n=n/x;
    }
    return nr;
}
int main()
{
    f>>p>>q;
    d=2;
    while (p!=1 && d*d<=p)
    {
        exp=0;
        while (p%d==0)
        {
            exp++;
            p=p/d;
        }
        if (exp!=0)
        {
            step=1<<30;
            for (i=0; step; step>>=1)
            {
                if (verif(i+step,d)<q*exp)
                {
                    i+=step;
                }
            }
            if (i>Max) Max=i;
        }
        d++;
    }
    if (p!=1)
    {
        step=1<<30;
        for (i=0; step; step>>=1)
        {
            if (verif(i+step,p)<q)
            {
                i+=step;
            }
        }
        if (i>Max) Max=i;
    }
    g<<Max+1<<'\n';
    return 0;
}