#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("zero2.in");
ofstream fout("zero2.out");
ll t = 10, n, b, rez;

ll aflaPutere(ll nr) {
    ll put = 0;
    for (ll p = nr, f = 1; p <= n; p *= nr, ++f) {
        ll dim = min(p * nr, n + 1) - p;
        put += (f - 1) * dim + f * dim;
    }
    return put;
}

void desc() {
    ll div = 2, a = b;
    while (a > 1) {
        ll p = 0;
        while (a % div == 0)
            a /= div, ++p;
        if (p > 0)
            rez = min(rez, aflaPutere(div) / p);
        ++div;
        if (a > 1 && div * div > a)
            div = a;
    }
    return;
}

int main() {
    //cin >> n >> b;
    //cout << aflaPutere(b);
    //return 0;
    while (t--) {
        fin >> n >> b;
        rez = 1e12;
        desc();
        fout << rez << "\n";
    }
    return 0;
}