#include <cstdio>

using namespace std;

long long divizori[10],puteri[10],nrdiv;

void descompunere(long long n) {
    int d,p;
    d = 2;
    while (d * d <= n && n > 1) {
        p = 0;
        while (n % d == 0) {
            n = n / d;
            p++;
        }
        if (p > 0) {
            divizori[nrdiv] = d;
            puteri[nrdiv] = p;
            nrdiv++;
        }
        d++;
    }
    if (n > 1) {
        divizori[nrdiv] = n;
        puteri[nrdiv] = 1;
        nrdiv++;
    }
}

long long nrp(long long p,long long n) {
    long long baza = p,cnt = 0;
    while (p <= n) {
        cnt += n / p;
        p *= baza;
    }
    return cnt;
}

int main() {
    freopen("gfact.in","r",stdin);
    freopen("gfact.out","w",stdout);
    long long p,q,pas,i,j;
    pas = 1LL << 50;
    scanf("%lld%lld",&p,&q);
    descompunere(p);
    i = 0;
    while (pas) {
        for (j=0; j<nrdiv; j++)
            if (nrp(divizori[j],i + pas) < puteri[j] * q)
                i += pas;
        pas /= 2;
    }
    printf("%lld",i + 1);
    return 0;
}