#include<stdio.h>
#include<math.h>
#define LL long long
#define max(x,y) (x>y) ? x : y
using namespace std;
LL factors[2012],powers[2012];

void desc(int n)
{
LL d=2,e,limita;
limita=(LL)sqrt(n);
while(d<=limita && n>1)
{
    e=0;
    while((n%d)==0)
    {
        e++;
        n/=d;
    }
    if(e)
        {
            factors[++factors[0]]=d;
            powers[++powers[0]]=e;

        }
    d++;
}
if(n>1)
    {
        factors[++factors[0]]=n;
        powers[++powers[0]]=1;
    }
}

LL multi(LL p,LL n)
{
    LL num=p,s=0;
    while(n)
    {
        s+=n/num;
        n=n/num;
    }
return s;
}

LL cautare(LL fact,LL exp)
{
    LL pozdy=0,elfus,med,st=1,dr=(1ll<<61)-1;
    while(st<=dr)
    {
        med=(st+dr)>>1;
        elfus=multi(fact,med);
        if(elfus>=exp)
        {
            dr=med-1;
            pozdy=med;
        }
        else
            st=med+1;
    }
    return pozdy;
}

int main()
{
    LL p,q,sol=-1,i;

    freopen("gfact.in","r",stdin);
    freopen("gfact.out","w",stdout);

    scanf("%lld%lld",&p,&q);
    desc(p);

    for(i=1;i<=powers[0];i++)
        powers[i]*=q;

    for(i=1;i<=powers[0];i++)
        sol=max(sol,cautare(factors[i],powers[i]));
    printf("%lld",sol);
    return 0;
}