#include <stdio.h>
#include <stdlib.h>
int k=0,baza[50000],exp[50000];
long long legendre(long long z,long long n)
{
    long long x,p;
    x=0;
    p=1;
    while(p<=z)
    {
        p*=n;
        x=x+(z/p);
    }
    return x;
}
long long fact(long long z,long long q)
{
    long long i,rez;
    for(i=1; i<=k; i++)
    {
        rez=legendre(z,baza[i]);
        if(rez<q*exp[i])
            return 0LL;
    }
    return 1LL;

}
int main()
{
    long long p,q,d,e,i,pas;
    freopen("gfact.in","r",stdin);
    freopen("gfact.out","w",stdout);
    scanf("%lld%lld",&p,&q);
    d=2;
    k=0;
    while(d*d<=p)
    {
        e=0;
        while(p%d==0)
            p/=d,e++;
        if(e>0)
        {
            k++;
            baza[k]=d;
            exp[k]=e;
        }
    }
    if(p>0)
    {
        k++;
        baza[k]=p;
        exp[k]=1;
    }
    i=0;
    pas=1LL<<60LL;
    while(pas!=0)
    {
        if(fact(i+pas,q)==0LL)
            i+=pas;
        pas/=2;
    }
    printf("%lld\n",i+1);

    return 0;
}