#include<bits/stdc++.h>
using namespace std;
ifstream fin("gfact.in");
ofstream fout("gfact.out");

typedef long long LL;

LL p, q, tmp, ans;

LL pw(LL n, int p)
{
    LL r = 0;
    while(n) {
        n /= p;
        r += n;
    } return r;
}

void binary(int x, int power)
{
    LL i, step=1LL<<60;
    for(i=0; step; step>>=1)
        if(pw(i + step, power) < x)
            i += step;
    ans = max(ans, i+1);
}

int main()
{
    fin >> p >> q;
    for(int i=2; i*i<=p; ++i) {
        if(p%i == 0) {
            tmp = 0;
            while(p%i == 0) {
                p /= i;
                tmp += q;
            }
            binary(tmp, i);
        }
    }
    if(p > 1) {
        binary(q, p);
    }

    fout << ans;

    return 0;
}