#include <fstream>
#define nmax 700001

using namespace std;

ifstream fin("gfact.in");
ofstream fout("gfact.out");

long long p,q,pas,putere,maxx;

long long divide(long long n,long long x)
{
    long long r=0;
    while(n>=x)
    {
        r+=n/x;
        n/=x;
    }
    return r;
}

long long caut(long long a,long long b)
{
    long long r=0;
    pas=1<<30;
    pas=pas*pas;
    while(pas!=0)
    {
        if(divide(r+pas,a)<b && r+pas<=a*b)
            r+=pas;
        pas/=2;
    }
    return ++r;
}

int main()
{
    long long d=2,i;
    fin>>p>>q;
    while(p>1)
    {
        i=0;
        putere=0;
        if(d*d>p)
            d=p;
        while(!(p%d))
        {
            putere++;
            p/=d;
        }
        if(putere!=0)
            i=caut(d,putere*q);
        if(i>maxx)
            maxx=i;
        d++;
    }
    fout<<maxx;
    return 0;
}