#include <fstream>

using namespace std;
ifstream cin("gfact.in");
ofstream cout("gfact.out");
int power(int p,int n)
{
    int s=0;
    while(p<=n)
    {
        s+=n/p;
        p*=p;
    }
    return s;
}
int solve(int p,int n)
{
    int st,dr,m;
    st=0;
    dr=30;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(power(p,m)>n)
           dr=m-1;
        if(power(p,m)==n)
           return m;
        if(power(p,m)<n)
           st=m+1;
    }
    return st;
}
int main()
{
    int p,q,d=2,rez=0,pow;
    cin>>p>>q;
    while(d*d<=p)
    {
        pow=0;
        while(p%d==0)
        {
            p/=d;
            pow++;
        }
        pow*=q;
        rez=max(rez,solve(d,pow));
        d++;
    }
    if(p)
       rez=max(rez,solve(p,q));
    cout<<rez;
    return 0;
}