#include<fstream>
#include<fstream>
#define NMAX 50
#define ll long long
using namespace std;
ifstream f("gfact.in");
ofstream g("gfact.out");
int p,q,k,t[NMAX],r[NMAX];
int putere(int x, int y, ll z)
{   ll nr=0,pr=x;
    while(z/pr) nr+=z/pr, pr=pr*x;
    if (nr>=y) return 1;
    return 0;
}
int main()
{   f>>p>>q;
    if(!(p&1))
    {	t[++k]=2;
        while(!(p&1)) r[k]+=q, p/=2;
    }
    int d=3;
    while(d*d<=p)
    {   if(!(p%d))
        {   t[++k]=d;
            while(!(p%d)) r[k]+=q, p/=d;
        }
        d+=2;
    }
    if (p>1) t[++k]=p, r[k]=q;
	ll st,dr,mij,mx=-1,nr;
	for(int i=1;i<=k;++i)
    {   st=1; dr=(ll)t[i]*(ll)r[i]; mij=0;
        while(st<=dr && st!=mij)
        {   mij=(st+dr)/2;
            if(putere(t[i],r[i],mij)) dr=mij-1; else nr=mij,st=mij+1;
        }
        if (nr>mx)mx=nr;
    }
    g<<mx+1<<"\n";
    g.close();
    return 0;
}