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