#include <cstdio>

using namespace std;

FILE *in,*out;

const long long L = 60;
const long long n = 2000000000;

long long exp(long long x,long long baza)
{
    long long rez = 0;
    while(x > 0)
    {
        rez += x/baza;
        x /= baza;
    }
    return rez;
}

long long cauta(long long x,long long baza)
{
    long long pas = 1LL<<L,r = 0;
    while(pas > 0)
    {
        if(exp(r + pas,baza) < x)
            r += pas;
        pas /= 2;
    }
    return r+1;
}

int main()
{
    in = fopen("gfact.in","r");
    out = fopen("gfact.out","w");
    long long p,q;
    fscanf(in,"%lld %lld",&p,&q);
    long long d = 2,cp;
    long long r,maxim = -99;
    cp = p;
    while(d * d <= cp)
    {
        long long putere = 0;
        while(cp % d == 0)
        {
            putere ++;
            cp /= d;
        }
        r = cauta(putere*q,d);
        if(r > maxim) maxim = r;
        d++;
    }
    if(cp > 1)
        r = cauta(q,cp);
    if(r > maxim) maxim = r;
    fprintf(out,"%lld",r);
    return 0;
}