#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;
typedef unsigned int ui;

ui k, n;

ui minn(ui a, ui b) {
    if (a < b)
        return a;
    return b;
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> n >> k;

    ui t = k, ch = 2, ans = 10000000000;
    while (t > 1) {
        ui pk = 0, pn = 0; ll nn = ch;
    if (t % ch == 0) {
            while (t % ch == 0) {
                t /= ch;
                ++pk;
            }
            while (nn <= n) {
                pn += n / nn;
                nn *= ch;
            }
            ans = minn(pn / pk, ans);
        }
        ++ch;
    }

    cout << ans << endl;

    return 0;
}