#include <fstream>

using namespace std;
ifstream cin("gfact.in");
ofstream cout("gfact.out");
int power(int p,int n)
{
    int s=0,cp=p;
    while(p<=n)
    {
        s+=n/p;
        p*=cp;
    }
    return s;
}
int solve(int p,int q)
{
    int st,dr,m;
    st=0;
    dr=30;
    bool ok=1;
    while(st<=dr&&ok)
    {
        m=(st+dr)/2;
        if(power(p,m)>q)
           dr=m-1;
        if(power(p,m)<q)
           st=m+1;
        if(power(p,m)==q)
           {
               ok=0;
               st=m;
           }
    }
    return st-st%p;
}
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;
}