#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;
struct DESCOMPUNERE
{
    int p,e;
};
DESCOMPUNERE d[100];
int u;
inline int legendre(int p,int n)
{
    int s=0;
    while(n)
    {
        s+=n/p;
        n/=p;
    }
    return s;
}
inline int bs(int st,int dr,int poz)
{
    int med,last=-1;
    while(st<=dr)
    {
        med=st+((dr-st)>>1) ;
        if (legendre(d[poz].p,med)>=d[poz].e)
            last=med,dr=med-1;
        else
            st=med+1;
    }
    return last;
}
int main()
{
    freopen("gfact.in","r",stdin);
    freopen("gfact.out","w",stdout);
    int p,q,b,e,i,B=-1,intmax;
    intmax=INT_MAX;
    scanf("%d%d",&p,&q);
    b=2;
    while(b*b<=p && p>1)
    {
        e=0;
        while(p%b==0)
        {
            p/=b;
            ++e;
        }
        if (e)
        {
            ++u;
            d[u].p=b;
            d[u].e=e*q;
        }
        ++b;
    }
    if(p>1)
    {
        ++u;
        d[u].p=p;
        d[u].e=q;
    }
    for(i=1; i<=u; ++i)
        B=max(B,bs(1,intmax,i));
    printf("%d\n",B);
    return 0;
}