#include<cstdio>
#include<math.h>
using namespace std;
struct Doica
{
    int x,y;
};

Doica v[15];
long long legendre(long long p,long long n)
{
    long long s=0;
    while(n)
    {
        s+=(n/p);
        n/=p;
    }
    return s;
}

long long bs(long long poz)
{
    long long med,last=-1;
    long long st=1;
    long long dr=((1LL<<60)-1);
    while(st<=dr)
    {
        med=st+((dr-st)>>1);
        if(legendre(v[poz].x,med)>=v[poz].y)
        {
            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,max=0,nr,x,nr1=0,i,k;
    scanf("%lld%lld",&p,&q);
    x=2;
    while(x*x<=p&&p>1)
    {
        nr=0;
        if(p%x==0)
        {
            while(p%x==0)
            {
                nr++;
                p/=x;
            }
            v[++nr1].x=x;
            v[nr1].y=nr*q;
        }
        x++;
    }
    if(p>1)
    {
        v[++nr1].x=p;
        v[nr1].y=q;
    }
    for(i=1;i<=nr1;++i)
    {
        k=bs(i);
        if(max<k)
            max=k;
    }
    printf("%lld\n",max);
    return 0;
}