#include <fstream>

using namespace std;

ifstream in("gfact.in");
ofstream out("gfact.out");

const long long N = 120001;

long long p, q, b, prim[N];

long long putere(long long poz, long long x) {
    long long nr = 0;

    while (x != 0) {
        x /= poz;
        nr += x;
    }

    return nr;
}

void cautbin(long long poz) {
    long long r = 0, pas = 1LL << 52;

    while (pas != 0) {
        if (r + pas <= q * poz * prim[poz] && putere(poz, r + pas) < q * prim[poz]) {
            r += pas;
        }
        pas >>= 1;
    }

    b = max(b, r + 1);
}

void precalc_prime(long long nr) {
    bool isprim = true;
    long long cp = p;

    for (long long d = 2; d * d <= p; d++) {
        while (cp % d == 0) {
            prim[d]++;
            cp /= d;
            isprim = false;
        }
        if (prim[d] != 0) cautbin(d);
    }

    if (isprim) {
        prim[p]++;
        cautbin(p);
    }
}

int main()
{
    in >> p >> q;
    precalc_prime(p);
    out << b;
    out.close();
}