#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;
struct DESCOMPUNERE
{
    long long p,e;
};
DESCOMPUNERE d[50];
long long u;
inline long long legendre(long long p,long long n)
{
    long long s=0;
    while(n)
    {
        s+=n/p;
        n/=p;
    }
    return s;
}
inline long long bs(long long st,long long dr,long long poz)
{
    long long 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);
    long long p,q,b,e,B=-1,long longmax;
    long longmax=long long_MAX;
    scanf("%lld%lld",&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(register long long i=1; i<=u; ++i)
        B=max(B,bs(1,long longmax,i));
    prlong longf("%lld\n",B);
    return 0;
}